[POJ][1703][并查集] Find them, Catch them

题目大意：

对于一些黑帮成员，你知道他们某些人不是一个团伙的，并以此判断另外一些人是否属于同一团伙。

思路：

并查集。难点在于对两个节点是否属于同一集合的判断。

代码：

#include
#include
using namespace std;
int n,m,f[100001];
//f[i]表示节点i的父节点。 
bool same[100001];
//same[i]=true表示节点i与其父节点属于同一集合。 
void init()
//初始化 
{
    for(int i=1;i<=n;i++)
    { 
        f[i]=i;
        //将每个节点的父节点初始化为其自身。 
        same[i]=true;
        //相应地，自身属于同一集合。 
    }
}
int find(int x)
//找到x的父节点。 
{
    if(x!=f[x])
    {
        int px=f[x];
        //px为更新前x的父节点。 
        f[x]=find(f[x]);
        if(same[x]&&!same[px])
        //px节点已经访问结束，所以same[px]已经被更新，px的父节点和x的父节点相同。
        //当前same[x]表示x与px是否属于同一集合，same[px]表示px和x与px新的共同的父节点是否属于同一集合。 
            same[x]=false;
            //根据same[x]与same[px]来更新same[x]。更新后的same[x]表示x与新父节点是否属于同一集合。 
        else if(!same[x]&&!same[px])
            same[x]=true;
    }
    return f[x];
}
void union_set(int x, int y)
{
    int px=find(x);
    int py=find(y);
    if(px!=py)
    {
        f[px]=py;
        if(same[x]==same[y])
            same[px]=same[px]?false:true;
    }
}
int main()
{
    int t;
    for(scanf("%d",&t);t>0;t--)
    {
        scanf("%d%d",&n,&m);
        init();
        for(int i=0;i