1: /************************************************************************/
2: /* *Author:justinzhang
3: /*Email:uestczhangchao@gmail.com
4: /*Establish:2011年5月14日16:43:46
5: /*Discription：算法导论22章并查集 */
6: /************************************************************************/
7:
8: #include
9: using namespace std;
10:
11: /*
12: *rank[]是用来存放元素x秩的数组，p[]是用来存放元素x父节点的数组
13: *Make_Set()用来初始化集合元素，刚开始的时候每个元素独立为一个集合
14: */
15: void Make_Set(int rank[],int p[],int x)
16: { 17: p[x] = x;
18: rank[x] = 0;
19: }
20:
21: /************************************************************************/
22: /* 寻找x元素所属的集合 */
23: /************************************************************************/
24: int Find_Set(int p[],int x)
25: { 26: if(p[x]!=x)
27: { 28: p[x] = Find_Set(p,p[x]);
29: }
30:
31: return p[x];
32:
33: }
34:
35:
36: /************************************************************************/
37: /* 合并两个集合 */
38: /************************************************************************/
39: void Union(int rank[],int p[],int x, int y)
40: { 41: int px = Find_Set(p,x);
42: int py = Find_Set(p,y);
43: if (rank[px]>rank[py])
44: { 45: p[py] = px;
46: }
47: else
48: { 49: p[px] = py;
50: if (rank[px]==rank[py])
51: { 52: rank[py]++;
53: }
54: }
55: }
56:
57: int main()
58: { 59: int n, m;
60: int rank[30003];
61: int p[30003];
62: int numsuspect;
63: int personnum;
64: int firstpersonnum;
65: int groupnum;
66: int i,j;
67: while(1)
68: { 69: numsuspect = 0;
70: memset(rank,0,sizeof(rank));
71: memset(p,0,sizeof(p));
72: cin >> n >> m;//n为学生人数，m为学生的分组数
73: if(n==0 && m==0)
74: break;
75: for(j=0;j
76: Make_Set(rank,p,j);
77: while((--m)>=0)
78: { 79: cin>>groupnum;
80: if (groupnum>=1)
81: { 82: cin>>firstpersonnum;
83: }
84:
85: for(i=1;i
86: { 87: cin >> personnum;
88: Union(rank,p,firstpersonnum,personnum);
89: }
90:
91: }
92: for (j=0;j
93: { 94: if (Find_Set(p,0)==Find_Set(p,j))
95: { 96: numsuspect++;
97: }
98: }
99: cout << numsuspect << endl;
100:
101: }
102: system("pause"); 103: return 0;
104: }
105: