题目大意:
有一个人要过生日了,请他的朋友来吃饭,但是他的朋友互相认识的才能坐在一起,朋友的编号从1 ~ n,输入的两个数代表着这两个人互相认识(如果1和2认识,2和3认识,那么1和3也就认识了)。问需要多少桌子。
思路:
并查集的基础题目,pre数组存的是父节点的值,root数组代表是否为根节点。最后统计根节点的数量就可以了~~~~~
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <cstdlib> 5 #include <cmath> 6 #include <cctype> 7 #include <algorithm> 8 using namespace std; 9 const int MAXN = 1e3 + 3; 10 int pre[MAXN]; 11 bool root[MAXN]; 12 13 int Find(int x) 14 { 15 int r = x; 16 while(pre[r] != r) 17 { 18 r = pre[r]; 19 } 20 int i = x,j; 21 while(pre[i] != r) //路径压缩 22 { 23 j = i; 24 i = pre[i]; 25 pre[j] = r; 26 } 27 return r; 28 } 29 30 void mix(int a,int b) 31 { 32 int x = Find(a); 33 int y = Find(b); 34 if(x > y) 35 { 36 pre[x] = y; 37 } 38 if(x < y) 39 { 40 pre[y] = x; 41 } 42 } 43 44 int main() 45 { 46 int t; 47 scanf("%d",&t); 48 while(t--) 49 { 50 int M,N; 51 for(int i = 1; i <= MAXN; i++) 52 { 53 pre[i] = i; 54 root[i] = false; 55 } 56 scanf("%d%d",&M,&N); 57 while(N--) 58 { 59 int a,b; 60 scanf("%d%d",&a,&b); 61 mix(a,b); 62 } 63 for(int i = 1; i <= M; i++) 64 { 65 if(pre[i] == i) 66 root[i] = true; 67 } 68 int ans = 0; 69 for(int i = 1; i <= M; i++) 70 { 71 if(root[i]) ans ++; 72 } 73 printf("%d ",ans); 74 } 75 return 0; 76 }