POJ1703-Find them, Catch them 并查集构造

好久没有做并查集的题，竟然快把并查集忘完了。

题意：大致是有两个监狱，n个犯人，m次操作，每次操作可以是查询也可以是确定两个人是否在同一个监狱里。

思路：其实这题完全可能做出来，结果就是没做出来。理清思路还是很好想的，我们用一个并查集来把能够确定在同一监狱里的人放在一个集合里，用一个diff数组把确定不同监狱的两个犯人分别与对方不同监狱的犯人放在一个集合里，就是这么简单。

const int N=1e5+10;

int f[N],dif[N];

char s[5];

void init()

{

    for(int i=0;i<N;i++) f[i]=i;

    memset(dif,-1,sizeof(dif));

}

int find(int x)

{

    return f[x]==x?x:f[x]=find(f[x]);

}

int main()

{

    int t,n,m;

    scanf("%d",&t);

    while(t--)

    {

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

        init();

        int u,v;

        while(m--)

        {

            scanf("%s%d%d",s,&u,&v);

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

            {

                if(find(u)==find(v)) printf("In the same gang.\n");

                else if(find(dif[u])==find(v)||find(dif[v])==find(u))  printf("In different gangs.\n");

                else printf("Not sure yet.\n");

            }

            else

            {

                if(dif[u]==-1) dif[u]=v;

                if(dif[v]==-1) dif[v]=u;

                int uu=find(dif[u]),vv=find(dif[v]);

                f[uu]=find(v);

                f[vv]=find(u);

            }

        }

    }

    return 0;

}

巴特西

POJ1703-Find them, Catch them 并查集构造

最新文章

热门文章