并查集-HDU 1213-How Many Tables

并查集-HDU 1213-How Many Tables

题目链接：How Many Tables
并查集基础：

数据结构-并查集

思路：

题目大意：

一位哥过生日请了N个朋友，为了避免尴尬，没有交际的朋友之间不能在同一张桌子，给定M个人际关系，问需要安排的桌子数。

题解：

题目说得很明确，如果一个人在一个圈子中找到自己认识的人，那他也是这个圈子的人，就可以坐在一起（当然我个人不太认同这个说法，不过这是题目），桌子还没有限制人数，很明显并查集水题

把每个圈子描述成一个集合，通过给定的人际关系，比如给定 a b 认识，但此先a，b两个圈子并没有交集，但因为a b 是认识的，所以a的圈子与b的圈子实际上是一个交际圈，可以坐在一张桌子

确定人际关系后，统计集合个数便是所需桌子数量

统计的话我是用set，因为set有去重的作用，如果多个朋友在同个圈子只要记录一次

代码：

include

using namespace std;

define MAX_SIZE 1024

int Friends[MAX_SIZE];

void Init(int n)
{

for(int i=0;i<=n;i++)
    Friends[i]=-1;

}

int Find(int Index )
{

if(Friends[Index]==-1)
    return Index;
else
    return Find(Friends[Index]);

}

void Combine(int a,int b)
{

int a_root=Find(a);
int b_root=Find(b);
if(a_root!=b_root)    //a b是认识的，如果原先各自圈子没有交集，就合并
    Friends[a_root]=b_root;

}

int main()
{

int T,M,N;
cin>>T;
while(T--)
{
    int Res=0;
    set<int> Table;
    cin>>N>>M;
    Init(N);
    while(M--)
    {
        int a,b;
        cin>>a>>b;
        Combine(a,b);
    }
    for(int i=1;i<=N;i++)   //统计集合个数
        Table.insert(Find(i));
    Res=Table.size();
    cout<<Res<<endl;
}
return 0;