pku 1611

2009年7月12日 星期日

题目链接：PKU 1611 The Suspects

分类：最基础的并查集


Code:

 1#include<iostream>
 2using namespace std;
 3#define MAXN 30000
 4int parent[MAXN];
 5
 6void init(int n=MAXN)
 7{
 8    int i;
 9    for(i=0;i<n;i++)parent[i]=-1;
10}
11int find(int x)
12{
13    if(parent[x]<0) return x;
14    else return parent[x]=find(parent[x]);
15}
16
17int Union(int x,int y)
18{
19    int root1=find(x),root2=find(y);
20    if(root1==root2) return root1;
21    if(parent[root1]<parent[root2])
22    {
23        parent[root1]+=parent[root2];
24        parent[root2]=root1;
25        return root1;
26    }
27    else
28    {
29        parent[root2]+=parent[root1];
30        parent[root1]=root2;
31        return root2;
32    }
33}
34
35int main()
36{
37    int n,m,root,i,k,j,node;
38    while(scanf("%d%d",&n,&m)!=EOF)
39    {
40        if(!n&&!m)break;
41        init(n);
42        for(i=0;i<m;i++)
43        {
44            scanf("%d",&k);
45            for(j=0;j<k;j++)
46            {
47                scanf("%d",&node);
48                if(j==0)root=node;
49                root=Union(root,node);
50            }
51        }
52        printf("%d\n",-parent[find(0)]);
53    }
54    return 0;
55}
56
57

posted on 2009-07-12 22:53 蜗牛也Coding 阅读(815) 评论(0)  编辑 收藏 引用


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


<2009年7月>
日一二三四五六
2829301234
567891011
12131415161718
19202122232425
2627282930311
2345678

导航

统计

常用链接

留言簿(8)

随笔档案(78)

搜索

积分与排名

最新评论

阅读排行榜

评论排行榜