并查集基本知识看：http://blog.csdn.net/dellaserss/article/details/7724401
题意：假设一张桌子可坐无限多人，小明准备邀请一些朋友来，所有有关系的朋友都可以坐同一张桌，没有关系的则要另开一桌，问需要多少张桌子（小明不坐，不考虑小明与其他人的关系）？
思路：常规的并查集。要求出所有人的老大，有几个老大就要几张桌子。那么有关系的都归为同一个老大。用数组实现，再顺便压缩路径。
#include <bits/stdc++.h>
#define LL long long
using namespace std;
const int N=;
int pre[N]; //结点i的上级
inline void init(int n){for(int i=; i<=n; i++) pre[i]=i;} //将上级初始化为自己 int find(int x) //找x的上级
{
int k=x;
while(pre[x]!=x) x=pre[x]; //找上级
int tmp;
while(pre[k]!=x) //优化:路径压缩
{
tmp=pre[k];
pre[k]=x;
k=tmp;
}
return x;
} void joint(int a,int b) //将a和b合并为一个集合
{
a=find(a);
b=find(b);
if(a!=b) pre[a]=b;
} int check(int n) //查查到底需要几张桌子
{
set<int> sett;
for(int i=; i<=n; i++) find(i); //防漏网之鱼，将所有人的老大推到最顶。
for(int i=; i<=n; i++) sett.insert(pre[i]);
return sett.size();
}
int main()
{
//freopen("e://input.txt", "r", stdin);
int t, n, m, a, b;
cin>>t;
while(t--)
{
scanf("%d%d", &n, &m);
init(n);
for(int i=; i<m; i++)
{
scanf("%d%d",&a,&b);
joint(a,b);
}
printf("%d\n",check(n));
}
return ;
}
AC代码