并查集或者DFS的題，大概是說(shuō)有N個(gè)學(xué)生去訂房間，只有朋友可以住一個(gè)房間。朋友關(guān)系具有傳遞性，如果A和B是朋友,B和C是朋友，那么A和C是朋友。問(wèn)最后最少定多少個(gè)房間。
我用并查集做，卻在最后犯了一個(gè)很不容易發(fā)覺(jué)的錯(cuò)誤，最后還是找一個(gè)學(xué)姐才發(fā)現(xiàn)。看來(lái)以后一定得小心啊，太大意會(huì)很可怕的~
Code：
1 #include<stdio.h>
2 #include<string.h>
3 struct student
4 {
5 int father,rank;
6 }a[250];
7 bool flag[250];
8 void initial(int n)
9 {
10 int i;
11 for(i=1;i<=n;i++){
12 a[i].father=i;
13 a[i].rank=1;
14 }
15 }
16 int find(int n)
17 {
18 while(a[n].father!=n)
19 n=a[n].father;
20 return n;
21 }
22 void Union(int root1,int root2)
23 {
24 int t1,t2;
25 t1=find(root1);
26 t2=find(root2);
27 if(t1==t2) return ;
28 else{
29 if(a[t1].rank>a[t2].rank){
30 a[t2].father=t1;
31 a[t1].rank+=a[t2].rank;
32 }
33 else{
34 a[t1].father=t2;
35 a[t2].rank+=a[t1].rank;
36 }
37 }
38 }
39 int main()
40 {
41 int i,j,k,m,n,cas;
42 scanf("%d",&cas);
43 while(cas--){
44 scanf("%d%d",&n,&m);
45 initial(n);
46 for(i=1;i<=m;i++){
47 scanf("%d%d",&j,&k);
48 Union(j,k);
49 }
50 memset(flag,false,sizeof(flag));
51 k=0;
52 for(i=1;i<=n;i++){
53 if(!flag[find(i)]){
54 k++;
55 flag[find(i)]=true;
56 }
57 }
58 printf("%d\n",k);
59 }
60 }
61