首页 > 代码库 > POJ - 1703 Find them, Catch them(种类并查集)
POJ - 1703 Find them, Catch them(种类并查集)
题意：N个人，M条关系，A x y表示询问x和y是不是属于同一组，D x y表示x和y是不同组。输出每个询问后的结果。
分析：
1、所有的关系形成一个连通图，如果x和y可达，那两者关系是确定的，否则不能确定。
2、r[tmpy] = r[x] + r[y] + 1;可以更新连通块里祖先的标号。
eg：
5 4
D 1 2
D 2 3
D 4 5-----到此为止形成两个连通块，标号如图所示（红笔）
D 3 5
第四步，将3和5连边，因为以0为祖先，所以4的标号应当改变，可以发现改变后的r[4] = r[3] + r[5] + 1 = 2 + 1 + 1 = 4;
3、r[5]的更新在Find函数里完成。(Find函数更新原连通块里除祖先外的结点)
int tmp = Find(fa[x]);//更新5的原祖先4的权值
r[x] += r[fa[x]];//通过加上原祖先4的新权值以完成更新。
#pragma comment(linker, "/STACK:102400000, 102400000")#include<cstdio>#include<cstring>#include<cstdlib>#include<cctype>#include<cmath>#include<iostream>#include<sstream>#include<iterator>#include<algorithm>#include<string>#include<vector>#include<set>#include<map>#include<stack>#include<deque>#include<queue>#include<list>#define Min(a, b) ((a < b) ? a : b)#define Max(a, b) ((a < b) ? b : a)const double eps = 1e-8;inline int dcmp(double a, double b){ if(fabs(a - b) < eps) return 0; return a > b ? 1 : -1;}typedef long long LL;typedef unsigned long long ULL;const int INT_INF = 0x3f3f3f3f;const int INT_M_INF = 0x7f7f7f7f;const LL LL_INF = 0x3f3f3f3f3f3f3f3f;const LL LL_M_INF = 0x7f7f7f7f7f7f7f7f;const int dr[] = {0, 0, -1, 1, -1, -1, 1, 1};const int dc[] = {-1, 1, 0, 0, -1, 1, -1, 1};const int MOD = 1e9 + 7;const double pi = acos(-1.0);const int MAXN = 1e5 + 10;const int MAXT = 10000 + 10;using namespace std;int r[MAXN];int fa[MAXN];void init(){ for(int i = 0; i < MAXN; ++i){ fa[i] = i; r[i] = 0; }}int Find(int x){ if(fa[x] == x) return x; int tmp = Find(fa[x]); r[x] += r[fa[x]]; return fa[x] = tmp;}int main(){ int T; scanf("%d", &T); while(T--){ init(); int N, M; scanf("%d%d", &N, &M); for(int i = 0; i < M; ++i){ char a; int x, y; getchar(); scanf("%c%d%d", &a, &x, &y); int tmpx = Find(x); int tmpy = Find(y); if(a == ‘D‘){ if(tmpx == tmpy) continue; if(tmpx < tmpy){ fa[tmpy] = tmpx; r[tmpy] = r[x] + r[y] + 1; } else{ fa[tmpx] = tmpy; r[tmpx] = r[x] + r[y] + 1; } } else if(a == ‘A‘){ if(tmpx != tmpy){ printf("Not sure yet.\n"); continue; } if(abs(r[y] - r[x]) & 1){ printf("In different gangs.\n"); } else{ printf("In the same gang.\n"); } } } } return 0;}
POJ - 1703 Find them, Catch them(种类并查集)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。