题意：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 #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #define Min(a, b) ((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
POJ - 1703 Find them, Catch them(种类并查集)
京公网安备 11010802041100号