首页 > 代码库 > POJ 1703 Find them, catch them (并查集)
POJ 1703 Find them, catch them (并查集)
题目： Find them,Catch them
刚开始以为是最基本的并查集，无限超时。
这个特殊之处，就是可能有多个集合。
比如输入D 1 2 D 3 4 D 5 6...这就至少有3个集合了。并且任意2个集合之间成员的敌我关系不明。
这里每个集合里面的成员关系要记录，他们在一个集合里，只是因为他们关系明确，敌人或者朋友。
千万不要简单的认为成朋友在一个集合，敌人在另外一个集合，分成2个集合。因为题目说只有2个匪帮，很容易进入这个误区。
我们只要记录一个成员和自己父亲的敌我关系和建树就可以了。
代码：
#include<iostream>#include<cstdio>using namespace std;const int MM = 100001;int father[MM];int relation[MM];int find(int x){ if(x == father[x]) return x; int r = find(father[x]); relation[x] ^= relation[father[x]]; return father[x] = r;}void join(int x, int y){ int fx = find(x); int fy = find(y); father[fx] = fy; if(relation[y] == 1) relation[fx] = relation[x]; else relation[fx] = 1 - relation[x];}void solve(){ int T,N,M,i,a,b,ta,tb; char str; scanf("%d", &T); while(T--) { scanf("%d %d",&N, &M); for(i = 1; i <= N; ++i) { father[i] = i; relation[i] = 0; } for(i = 0; i < M; ++i) { getchar(); scanf("%c %d %d", &str, &a, &b); if(str == ‘D‘) join(a, b); else { ta = find(a); tb = find(b); if(ta == tb) { if(relation[a] == relation[b]) printf("In the same gang.\n"); else printf("In different gangs.\n"); } else printf("Not sure yet.\n"); } } }}int main(){ solve(); return 0;}
POJ 1703 Find them, catch them (并查集)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。