首页 > 代码库 > POJ 1703 Find them, Catch them (并查集)
POJ 1703 Find them, Catch them (并查集)
题目大意:
有n个罪犯被逮到。他们分别属于两个团伙。而且每个团伙里至少有一个人
D a b 说明 a b 不是一个团伙的。
A a b 询问a b 是不是一个团伙的。
思路分析:
开始想的是如果a b 不是一个团伙,就把a 和 n+1 并,b和n+2 并。
但是看看下面这组数据就知道是错了。
1
4 4
D 1 2
D 3 4
D 1 4
A 1 3
不是直接的赋予一个集合。
那么正确思路就是在并查集上的运用。。
记录下他与父亲的关系。0 1 代表分别属于不同的集合。
find 的时候要更新自己的 opp 。这样保证每次合并集合的时候它都与根节点有最新的信息。
#include <cstdio> #include <iostream> #include <algorithm> #include <cstring> #define maxn 100005 using namespace std; int opp[maxn]; int pre[maxn]; int find(int x) { if(x==pre[x])return pre[x]; int t=pre[x]; pre[x]=find(t); opp[x]^=opp[t]; return pre[x]; } int main() { int T; scanf("%d",&T); while(T--) { int n,m; scanf("%d%d",&n,&m); for(int i=1;i<=n;i++){ pre[i]=i; opp[i]=0; } while(m--){ char str[2]; int a,b; scanf("%s%d%d",str,&a,&b); if(str[0]=='A'){ int x=find(a),y=find(b); if(n==2)printf("In different gangs.\n"); else if(x==y){ if(opp[a]==opp[b])printf("In the same gang.\n"); else printf("In different gangs.\n"); } else printf("Not sure yet.\n"); } else { int x=find(a),y=find(b); if(x!=y){ pre[y]=x; opp[y]=(opp[a]^1^opp[b]); } } } } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。