ZOJ-2833* 交友问题
一群人相互交友。M 1 2 代表1和2成为朋友 Q 1 代表查询1的朋友数。
Sample Input
3 5
M 1 2
Q 1
Q 3
M 2 3
Q 2
5 10
M 3 2
Q 4
M 1 2
Q 4
M 3 2
Q 1
M 3 1
Q 5
M 4 2
Q 4
Sample Output
Case 1:
2
1
3
Case 2:
1
1
3
1
4
思路：并查集问题。
#include<iostream>using namespace std;#include<memory.h>#include<stdio.h>int disjoinset[100001];int find(int * s,int x){if(s[x] <= 0)return x;elsereturn s[x] = find(s,s[x]); //path compress}void unionbysize(int *s,int root1,int root2){if(s[root1] <= s[root2]) //root1 is bigger{s[root1] = s[root1] + s[root2];s[root2] = root1;}else{s[root2] = s[root1] + s[root2];s[root1] = root2;}}//并查集内容 负数代表个数，正数代表父节点int main(){int N;int M;char type;int mem1;int mem2;int root1;int root2;int i = 0;bool isfirst = true;while(scanf("%d%d",&N,&M) != EOF){memset(disjoinset,-1,100001*sizeof(int));if(!isfirst)printf("\n");isfirst = false;printf("Case %d:\n",++i);while(M--){getchar(); scanf("%c",&type);if(type == 'M'){scanf("%d%d",&mem1,&mem2);root1 = find(disjoinset,mem1);root2 = find(disjoinset,mem2);if(root1 != root2)unionbysize(disjoinset,root1,root2);}else if(type == 'Q'){scanf("%d",&mem1);root1 = find(disjoinset,mem1);printf("%d\n",-disjoinset[root1]);}}}}