首页 > 代码库 > poj 1703 Find them, Catch them (并查集)
poj 1703 Find them, Catch them (并查集)
链接:poj 1703
题意:在这个城市里有2个黑帮团伙,现在给出N个人,M条信息
输入D x y代表x于y不在一个团伙里
输入A x y要输出x与y是否在同一团伙或者不确定他们在同一个团伙里
分析:虽说是并查集的题,但又有所不同,
本题给出的信息为x,y不在一个团伙,而并查集确定的是关于有关系的操作
假设x与x+N不在一个团伙,y与y+N不在一个团伙,又x与y不在一个团伙,
一共只有2个黑帮团伙,所以x与y+N在一个团伙,y与x+N在一个团伙,
这样就可以将无关系的信息,转化为有关系,再用并查集即可,
但是若x与y不在一个相同的团伙,得确定他们关系无法确定还是确定不在一个团伙
同理可以判断x与y+N的关系和y与x+N的关系即可
#include<stdio.h> #define M 200000 int f[M+5]; int find(int x) { if(x!=f[x]) f[x]=find(f[x]); return f[x]; } void mix(int a,int b) { a=find(a); b=find(b); if(a!=b) f[a]=b; } int judge(int a,int b) { a=find(a); b=find(b); if(a!=b) return 0; return 1; } int main() { int T,n,m,i,a,b; char c; scanf("%d",&T); while(T--){ scanf("%d%d",&n,&m); getchar(); for(i=1;i<=n*2;i++) f[i]=i; for(i=1;i<=m;i++){ scanf("%c%d%d",&c,&a,&b); getchar(); if(c=='D'){ mix(a,b+n); //a与b+n在一个团伙 mix(b,a+n); //b与a+n在一个团伙 } else if(c=='A'){ if(judge(a,b)) printf("In the same gang.\n"); else if(judge(a,b+n)||judge(b,a+n)) //若不在同一团伙,得判断是否无法确定关系 printf("In different gangs.\n"); else printf("Not sure yet.\n"); } } } return 0; }
poj 2492 也是同样的题型,直接改改输入输出就ok
链接:poj 2492
poj 1703 Find them, Catch them (并查集)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。