posts - 100,  comments - 15,  trackbacks - 0
 1#include<iostream>
 2using namespace std;
 3#define MAXN 30000
 4#define MAXM 500
 5
 6int parent[MAXN];
 7
 8void init(int n=MAXN)
 9{
10    int i;
11    for(i=0;i<n;i++)
12        parent[i]=-1;
13}

14int find(int x)
15{
16    if(parent[x]<0)
17        return x;
18    else return parent[x]=find(parent[x]);
19}

20
21int Union(int x,int y)
22{
23    int root1=find(x),
24        root2=find(y);
25    if(root1==root2) return root1;
26    if(parent[root1]<parent[root2])
27    {
28        parent[root1]+=parent[root2];
29        parent[root2]=root1;
30        return root1;
31    }
else{
32        parent[root2]+=parent[root1];
33        parent[root1]=root2;
34        return root2;
35    }

36}

37int main()
38{
39    int n,m,i,j,k,x,root;
40    while( scanf("%d%d",&n,&m)==2 && n!=0 )
41    {
42        init(n);
43        for(i=0;i<m;i++)
44        {
45            scanf("%d",&k);
46                for(j=1;j<=k;j++)
47                {
48                    scanf("%d",&x);
49                    if(j==1) root=x;
50                    root=Union(root,x);
51                }

52        }

53        printf("%d\n",-parent[find(0)]);
54    }
        
55    return 0;
56}
posted on 2009-04-22 20:16 wyiu 阅读(192) 评论(0)  编辑 收藏 引用 所属分类: POJ

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   博问   Chat2DB   管理