本文主要是介绍poj 并查集 - 1703 Find them, Catch them，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
并查集题目，并的意思就是将两个不同类别的集合合并到一起，类似于两棵树合并；查的意思就是找到这个点所属集合的根节点。基本上并查集题目都是在大体架构上面加一些东西即可。并查集代码模板在这里点击打开链接
这道题目里里面有两个帮派，我们需要判断抓到的两个罪犯，是否属于一个帮派？D [a] [b] 说明a，b不是一个帮派，A[a][b]时需要判断这两个人是不是一个帮派的。
这里在并查集模板里加入一个ranks数组，用来说明这一个节点的人是属于0帮派还是1帮派。我们在find_set的时候就已经为每一个节点的ranks进行了%2操作，来保证该点和前驱结点不同，而和前驱结点的前驱结点相同。
#include <iostream>
using namespace std; const int MAXN = 100001;
int pa[MAXN];
int ranks[MAXN];void make_set(int n)
{/*创建一个单元集*/ int x;for(x=1;x<=n;x++){pa[x] = x;ranks[x]=0;}
} int find_set(int x)
{ int tem; if(x==pa[x]) return x; tem=pa[x]; pa[x]=find_set(tem); ranks[x]=(ranks[tem]+ranks[x])%2; return pa[x];
} void union_set(int x, int y)
{ int aa,bb; aa=find_set(x); bb=find_set(y); pa[bb]=aa; ranks[bb]=(ranks[x]+1-ranks[y])%2;
} int main()
{ int i,T,n,m,j;char k;scanf("%d",&T);while(T--){scanf("%d %d",&n,&m);make_set(n);while(m--){getchar();scanf("%c %d %d",&k,&i,&j);if(k == 'A'){if(find_set(i)==find_set(j)){if(ranks[i]==ranks[j])printf("In the same gang.\n");else printf("In different gangs.\n");}else printf("Not sure yet.\n");}else if(k=='D'){union_set(i,j);}}}return 0;
}
这篇关于poj 并查集 - 1703 Find them, Catch them的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
