The Suspects POJ - 1611

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
 #include <stdio.h>
 #define MAX_LENGTH 30005
 struct Union {
         int to;
         int rank;
 };
 Union Unions[MAX_LENGTH];
 void init_QucikUnion(int length){
   for (int i = 0;i<=length;i++){
     Unions[i].to = i;
     Unions[i].rank = 0;
     }
 }
 int Find(int n){
   while (Unions[n].to != n)
     n = Unions[n].to ;
   return n;
 }
 void Union(int i,int j){
   i = Find(i);
   j = Find(j);
   if (Unions[i].rank > Unions[j].rank) {
     Unions[j].to = i;
   } else {
     Unions[i].to = j;
     if (Unions[i].rank == Unions[j].rank) Unions[j].rank++;
   }
 }
 
 int main()
 {
   int N,M;
   while (scanf("%d%d",&N,&M) != EOF && (N != 0 || M != 0)){
     init_QucikUnion(N);
     Unions[0].rank = 30005;
     for (int i = 0;i<M;i++){
       int NS;
       scanf("%d",&NS);
       int numbers[30005];
       for (int j = 0;j<NS;j++){
         scanf("%d",&numbers[j]);
       }
       for (int k = 1;k<NS;k++){
         Union(numbers[k-1],numbers[k]);
       }
     }
     int suspects = 1;
     for (int i = 1;i<N;i++)
       if (Find(i) == 0)
         suspects++;
     printf("%dn",suspects++);
   }
   return 0;
 }