Find them, Catch them---poj1703（并查集）

题目链接：http://poj.org/problem?id=1703

可以认为n个人和m句话；

每句话包含A a b;D a b;

刚开始关系不确定；

A a b 就是问ab 是否同类；

D a b就是告诉我们ab不同类；

#include <iostream>
#include <cstdio>
#include <cstring>
#include <stdlib.h>
#include <math.h>
#include <queue>
#include <algorithm>
using namespace std;

const int oo = 0x3f3f3f3f;
const int N = 100050;

int f[N], r[N];///r[i]代表f[i]与i的关系，1代表不同类，0代表同类；

int Find(int x)
{
    int k=f[x];
    if(x!=f[x])
    {
        f[x] = Find(f[x]);
        r[x] = (r[x]+r[k])%2;
    }
    return f[x];
}

int main()
{
    int t;
    scanf("%d", &t);

    while(t--)
    {
        char s[10];
        int n, m, i, a, b, fa, fb;

        scanf("%d%d", &n, &m);

        for(i=0; i<=n; i++)
        {
            f[i] = i;
            r[i] = 0;
        }

        for(i=1; i<=m; i++)
        {
            scanf("%s%d%d", s, &a, &b);

            if(s[0]=='A')
            {


                fa = Find(a);
                fb = Find(b);

                if(fa!=fb)
                    printf("Not sure yet.
");
                else
                {
                    if(r[a]==r[b])
                        printf("In the same gang.
");
                    else
                        printf("In different gangs.
");
                }

            }
            else
            {
                fa = Find(a);
                fb = Find(b);

                if(fa!=fb)
                {
                    f[fa] = fb;
                    r[fa] = (r[b] - r[a] + 1 + 2)%2;
                }
            }
        }
    }
    return 0;
}