poj 1703 Find them, Catch them

Description

Input

Output

Sample Input

1
5 5
A 1 2
D 1 2
A 1 2
D 2 4
A 1 4

Sample Output

Not sure yet.
In different gangs.
In the same gang.

题解及代码：

         一开始的思路有问题，本来想将最开始的两个人设为基点，因为他们两个必然对立，然后看后来人和他们的关系来判断，后来的人的关系。但是会出现，后面的人与一开始的人没关系的情况，所以wa了。

1.开始改变思路，我们使用一个set数组来记录某个人对立阵营的一个人，当判断两个人的关系时，首先我们看两个人是否在同一个root中，如果在即为一个阵营，然后我们可以判断前一个人与后一个人的set中人物的关系，如果root相同即为不同阵营，否则就是还未确定。

#include <iostream>
#include <cstdio>
using namespace std;
int root[100010],set[100010];
int n,m;

void init()
{
    for(int i=0;i<=n;i++)
        root[i]=i,set[i]=0;
}


int look(int n)
{
    if(n!=root[n])
        root[n]=look(root[n]);
    return root[n];
}

void  _union(int a,int b)
{
    a=look(a);
    b=look(b);

    if(a==b) return;

    root[b]=a;
}


int main()
{
    int cas;
    scanf("%d",&cas);
    while(cas--)
    {
        scanf("%d%d",&n,&m);
        init();
        char s[2];
        int a,b;
        while(m--)
        {
            scanf("%s%d%d",s,&a,&b);
            if(s[0]=='A')
            {
                a=look(a);
                b=look(b);
                if(a==b)
                {
                    printf("In the same gang.\n");
                }
                else if(look(set[a])==b||look(set[b])==a)
                {
                    printf("In different gangs.\n");
                }
                else printf("Not sure yet.\n");
            }
            else
            {
                if(!set[a]&&!set[b]) {set[a]=b,set[b]=a;}
                else if(!set[a]) set[a]=b,_union(set[b],a);
                else if(!set[b]) set[b]=a,_union(set[a],b);
                else _union(set[a],b),_union(set[b],a);
            }
        }
    }

    return 0;
}

2.我们可以是一个数组来记录，每个节点与起父节点的关系，在查找和合并的时候都需要更新这个数组。

#include <iostream>
#include <cstdio>
using namespace std;
int root[100010],rela[100010];
int n,m;

void init()
{
    for(int i=0; i<=n; i++)
        root[i]=i,rela[i]=0;
}


int look(int n)
{
    int t=root[n];

    if(n!=root[n])
    root[n]=look(root[n]);

    rela[n]=(rela[n]==rela[t])?0:1;
    return root[n];
}

void  _union(int a,int b,int ra,int rb)
{
    root[rb]=ra;
    rela[rb]=(rela[a]==rela[b])?1:0;
}


int main()
{
    int cas;
    scanf("%d",&cas);
    while(cas--)
    {
        scanf("%d%d",&n,&m);
        init();
        char s[2];
        int a,b;
        while(m--)
        {
            scanf("%s%d%d",s,&a,&b);
            if(s[0]=='A')
            {
                int ra=look(a);
                int rb=look(b);
                if(ra==rb)
                {
                    if(rela[a]==rela[b])
                    printf("In the same gang.\n");
                    else printf("In different gangs.\n");
                }
                else printf("Not sure yet.\n");
            }
            else
            {
                int ra=look(a),rb=look(b);
                _union(a,b,ra,rb);
            }
        }
    }

    return 0;
}

poj 1703 Find them, Catch them,布布扣,bubuko.com

poj 1703 Find them, Catch them

原文：http://blog.csdn.net/knight_kaka/article/details/38513175