POJ 1703 Find them, Catch them

本文主要是介绍POJ 1703 Find them, Catch them，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

并查集的题目 ;

fa[ ] 表示父节点，ve[ ] 表示与父节点的关系。

f1 , v1 分别表示第一个人的父节点，与父节点的关系。f2 v2类似

如果两人父节点不同，则两人父节点之间的关系 为  (v1+v2+1)&1  ;

如果父节点相同，则两人的关系为 (v1+v2)&1 ;

int n,m; 
int fa[100001];
int ve[100001];//1表示不在一个帮派 
char a;int b,c;
void get(int x,int& f,int& v){ int r=x;v=0;while(r!=fa[r]){//路径压缩 v+=ve[r];r=fa[r];}fa[x]=f=r;ve[x]=v=v&1;
}int main(void)
{int T;cin>>T;FOR(TT,T){scanf("%d%d",&n,&m);FOR(i,n){//初始化 fa[i]=i;ve[i]=0;}FOR(T1,m){scanf(" %c%d%d",&a,&b,&c);int f1,v1,f2,v2;get(b,f1,v1);get(c,f2,v2);if(a=='D'){if(f1!=f2){//合并 fa[f1]=f2;ve[f1]=(v1+v2+1)&1;//f1与f2的关系就是 (v1+v2+1)&1}}else{if(f1!=f2) printf("Not sure yet.\n");else	if(((v1+v2)&1)==1) printf("In different gangs.\n");else printf("In the same gang.\n");}} }
return 0;
}

这篇关于POJ 1703 Find them, Catch them的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---