并查集

 1 #include<stdio.h>
 2 int n,m,parent[200010],b[200010];
 3 
 4 //初始化函数 
 5 void chushihua()
 6 {
 7     for (int i = 0; i <= n; i++)
 8         parent[i] = i;
 9 }
10 
11 //找根函数 
12 int  root_search(int t)
13 {
14     while(parent[t] != t)
15     {
16         t = parent[t];
17     }
18     return t;
19 }
20 
21 //合并函数 
22 void merge(int u,int v)
23 {
24     int t1 = root_search(u);
25     int t2 = root_search(v);
26     if (t1 != t2)
27         parent[t2] = t1;
28 }
29 
30 //主函数 
31 int main()
32 {
33     while(scanf("%d%d",&n,&m) && (m || n))
34     {
35         int k,index = 0;
36         chushihua();
37         for (int i = 0; i < m; i++)
38         {
39             scanf("%d",&k);
40             for (int j = 0; j < k; j++)
41             {
42                 scanf("%d",&b[j]);
43                 if (j > 0)
44                 {
45                     merge(b[j - 1], b[j]);
46                 }
47             }
48         }
49         for (int i = 0;i < n; i++)
50         {
51             if (root_search(i) == root_search(0))
52                 index++;
53         }
54         printf("%d\n",index);
55     }
56     return 0;
57 }

 

上一篇:比赛T1T2


下一篇:CodeForces 600B Queries about less or equal elements