首页 > 代码库 > POJ 1703 Find them, Catch them

POJ 1703 Find them, Catch them

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

 

思路:种类并查集。 并设置一个opp数组,opp[i]代表与i相对立的。

 

代码:

  

 

#include <iostream>#include <cstdio>using namespace std;int c,d;int t1,t2;int opp[100005];int f[100005];int getf(int x){    if(f[x] == x)    {        return x;    }    return f[x] = getf(f[x]);}void merge(int x,int y){    int a = getf(x);    int b = getf(y);        if(a!=b)    {        f[b] = a;    }}void init(){    for(int i=1;i<=t1;i++)    {        f[i] = i;        opp[i] = 0;    }}int main(){    int n;    scanf("%d",&n);    getchar();        char str[10];        while(n--)    {        scanf("%d %d",&t1,&t2);        getchar();        init();                for(int i=1;i<=t2;i++)        {            scanf("%s %d %d",str,&c,&d);            getchar();            if(str[0]==D)            {                if(opp[c]==0&&opp[d]==0)                {                    opp[c] = d;                    opp[d] = c;                }                else if(opp[c]==0)                {                    opp[c] = d;                    merge(opp[d],c);                }                else if(opp[d]==0)                {                    opp[d] = c;                    merge(opp[c],d);                                    }                else                {                    merge(opp[c],d);                    merge(opp[d],c);                }            }                else            {                if(t1==2)                {                        printf("In different gangs.\n");                        continue;                }                int temp1 = getf(c);                int temp2 = getf(d);                if(temp1==temp2)                {                    printf("In the same gang.\n");                }                else if(temp1 == getf(opp[d]))                {                    printf("In different gangs.\n");                }                else                {                    printf("Not sure yet.\n");                }            }        }    }    return 0;}

 

POJ 1703 Find them, Catch them