link:http://acm.sdibt.edu.cn:8080/judge/contest/view.action?cid=357#problem/D

题意是有两个帮派,现在告诉你一些互相敌对的点对,然后让你判断某两个点之间的关系首先判两个点关系是否确定;我的想法是构造假想敌,因为如果xy是敌人,则x和y的敌人就是朋友,就可以用并查集合并,这样还能确定之间的关系,比较好理解,如果xy是朋友,直接合并即可~~

code:

/*构造假想敌,x+n是x的敌人,则是y的朋友,y+n是y的敌人,则是x的朋友*/
#include <iostream>
#include <cstdio>
#define N 100005*2
using namespace std;
int a[N],rank[N];

int find(int x)
{
    if(x!=a[x])
        a[x]=find(a[x]);
    return a[x];
}

void merge(int x,int y)
{
    int xx=find(x);
    int yy=find(y);
    if(xx==yy)
        return;
    if(rank[xx]>rank[yy])
    {
	a[yy]=xx;
	rank[xx]+=rank[yy];
    }
    else
    {
	a[xx]=yy;
	rank[yy]+=rank[xx];
    }
}

int main()
{
    int n,m,t,x,y,i;
    char ch;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&n,&m);
        for(i=1;i<=n*2;i++)
            a[i]=i,rank[i]=1;/*成员,后n项思想是构造敌人*/
        while(m--)
        {
            getchar();
            scanf("%c%d%d",&ch,&x,&y);
            if(ch=='A')
            {
                if(find(x)==find(y))/*如果xy在一个集合,则说明在一个集合*/
                    printf("In the same gang.\n");
                else
                {
                    if(find(x+n)==find(y)||find(y+n)==find(x))/*xy不在一个集合时,判断x的敌人
                   是否是y的朋友*/
                        printf("In different gangs.\n");
                    else
                        printf("Not sure yet.\n");
                }
            }
            else
            {
                merge(x,y+n);/*x和y的敌人一个集合*/
                merge(y,x+n);/*y和x的敌人一个集合*/
            }
        }
    }
    return 0;
}

 

发表评论

电子邮件地址不会被公开。

Post Navigation