POJ 1703 Find them, Catch them
解法
union-findを使う。
人数の2倍の大きさのUF木を作って、
「AとBが違う」を unite(a, b+N), unite(a + N, b) とする。
A,Bが同じ根を持つなら同じグループ、A,B+Nが同じ根を持つなら違うグループとなり
どちらでもない場合は「まだ分からない」となる。
#include <cstdio> #include <vector> #include <algorithm> using namespace std; const int MAX_N = 100000; int uf[MAX_N * 2]; int N, M; void init(){ for(int i = 0; i < N * 2; i++) uf[i] = i; } int root(int p){ if(uf[p] == p) return p; return uf[p] = root(uf[p]); } bool is_same(int p, int q){ int t = root(p); int s = root(q); return (root(p) == root(q)); } void unite(int p, int q){ uf[root(p)] = root(q); } int main(){ int T; scanf("%d", &T); for(int i = 0; i < T; i++){ scanf("%d %d", &N, &M); init(); for(int i = 0; i < M; i++){ char c; int a, b; scanf("%c", &c); scanf("%c %d %d", &c, &a, &b); a--; b--; if(c == 'D'){ unite(a, b + N); unite(a + N, b); }else if(c == 'A'){ if(is_same(a, b)){ puts("In the same gang."); }else if(is_same(a + N, b)){ puts("In different gangs."); }else{ puts("Not sure yet."); } } } } }