比赛描述
在2014“华为杯”南邮大学生团体歌唱大赛每一个轮比赛现场，众多亲友团是一道亮丽的风景，他（她）们或来助威、或来观摩、或来刺探对手情报，不同亲友团之间偶尔还起冲突。为避免安全问题，主办方在赛场会划分许多独立区域，每一个区域安置一个亲友团，现在请你根据主办方提供的比赛现场信息，预测至多需要划分出多少个独立区域。
我们将主办方提供的比赛现场信息进行简化，从1开始按顺序给进入比赛现场的每位亲友分配一个编号，依次为1、2、...、K，K为亲友总数，为保护隐私，主办方只能告诉你M组两个不同亲友属于同一亲友团信息，这些信息有可能重复。
输入
输入包括多个测试用例，首先给出测试用例数N，接着给出N个测试用例，1≤N≤100。
每一个测试用例包括M+1行，首先给出两个整数K和M；再依次给出M行，每行给出两个不同正整数i和j，表示两个不同亲友i和j属于同一亲友团，i≠j，1≤i≤K，1≤j≤K，，1≤K≤10000，1≤M≤10000。
输出
输出包括多行，对于每个测试用例，输出一行，给出至多需要划分出的独立区域数量。
样例输入
2 3 1 1 2 3 2 1 2 2 3
样例输出
2 1
题目来源
SED
题意：有k个人，m组关系，同一关系则是同一组人，求最终组数。
分析：最基本的并查集。根据给定的关系生成并查集，最终i==pre[i]的数目即为组数。并查集理解： http://blog.csdn.net/qq_26071477/article/details/52075286。见AC代码：
//并查集 题目 #include<stdio.h> #include<set> using namespace std; const int maxn=10005; int pre[maxn]; int find(int x) //查找根节点 { int r=x; while (pre[r]!=r) //返回根节点 r r=pre[r]; int i=x,j ; while( i != r ) //路径压缩 { j=pre[i]; // 在改变上级之前用临时变量 j 记录下他的值 pre[i]=r ; //把上级改为根节点 i=j; } return r ; } void join(int x,int y) //判断x y是否连通， { int fx=find(x),fy=find(y); if(fx!=fy) pre[fx]=fy; //find(fx); //find(fy); //printf("%d 的上方为%d\n",fx,fy); } int main() { int T; scanf("%d",&T); while(T--) { int k,m; scanf("%d%d",&k,&m); for(int i=1; i<=k; i++) pre[i]=i; int i,j; while(m--) { scanf("%d%d",&i,&j); //if(find(i)!=find(j)) join(i,j); } /*set<int> s; for(int i=1; i<=k; i++) s.insert(find(i)); printf("%d\n",s.size()); s.clear();*/ //使用栈去重 int res=0; for(i=1;i<=k;i++) if(i==pre[i]) res++; //简化 pre等于自身的为头目 printf("%d\n",res); } } 是时候好好敲代码了。特记下，以备后日回顾。
