学步园

http://poj.org/problem?id=3256

对N个牧场用邻接表存储路径，记录下每个牧场初始牛的数目，沿路径dfs求连通牧场的牛数和。

code:

#include<cstdio>
#include<cstring>
using namespace std ;
int num[1001] ;
int sum[1001] ;
int head[1001] ;
bool vis[1001] ;
int x ;
struct past{
    int v, nex ;
}edge[10001] ;
void addedge(int u, int v){
    edge[x].v = v ;
    edge[x].nex = head[u] ;
    head[u] = x ;
    x ++ ;
}
void dfs(int a, int b){
    for(int i=head[a]; i; i=edge[i].nex){
        if(vis[edge[i].v])  continue ;
        vis[edge[i].v] = true ;
        sum[edge[i].v] += b ;
        dfs(edge[i].v, b) ;
    }
}
int main(){
    int n, m, k, i, u, v, ans ;
    while(~scanf("%d%d%d", &k, &n, &m)){
        memset(num, 0, sizeof(num)) ;
        memset(sum, 0, sizeof(sum)) ;
        for(i=0; i<k; i++){
            scanf("%d", &u) ;
            num[u] ++ ;
        }
        for(i=0; i<m; i++){
            scanf("%d%d", &u, &v) ;
            addedge(u, v) ;
        }
        for(i=1; i<=n; i++){
            memset(vis, false, sizeof(vis)) ;
            sum[i] += num[i] ;
            vis[i] = true ;
            dfs(i, num[i]) ;
        }
        ans = 0 ;
        for(i=1; i<=n; i++)
            if(sum[i]==k)   ans ++ ;
        printf("%d\n", ans) ;
    }
    return 0 ;}