首页 > > 程序设计 > C/C++ >

POJ 1703 Find them, Catch them 并查集，还是有…

2018-06-17 23:55:40来源：未知阅读 ()

题目不难理解，A判断2人是否属于同一帮派，D确认两人属于不同帮派。于是需要一个数组r[]来判断父亲节点和子节点的关系。具体思路可参考http://blog.csdn.net/freezhanacmore/article/details/8774033

#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;

const int maxn=100005;
int f[maxn];
int r[maxn];

int Find_f(int x)
{
    if (x != f[x])
    {
        int t=f[x];
        f[x] = Find_f(f[x]);
        r[x]=(r[x]+r[t])%2;
        return f[x];
    }
    return f[x];
}
void Union(int x,int y)
{
    int fx=Find_f(x);
    int fy=Find_f(y);
    f[fx]=fy;
    r[fx]=(r[x]+1+r[y])%2;
}
int main()
{
    //freopen("in.txt","r",stdin);
    int t;
    scanf("%d",&t);
    while(t--)
    {
        int n,m;
        scanf("%d%d",&n,&m);
        for(int i=1; i<=n; i++)
        {
            f[i]=i;
            r[i]=0;
        }
        char c;
        int crime1,crime2;
        while(m--)
        {
            getchar();
            scanf("%c%d%d",&c,&crime1,&crime2);
            //printf("%c\n",c);
            if(c=='D')
                Union(crime1,crime2);
            else if(c=='A')
            {
                if(Find_f(crime1)==Find_f(crime2))
                    if(r[crime1]!=r[crime2])
                        printf("In different gangs.\n");
                    else
                        printf("In the same gang.\n");
                else
                    printf("Not sure yet.\n");
            }
        }
    }
    return 0;
}