概要
2種類の集合があって,2つの要素が異なる集合に属しているという情報と,2つの要素が同じ集合に属すかどうか問うクエリが来る.
解法
蟻本の練習問題と同様の考え方を用いる.要素vについて,集合Aに属している事象Avと,集合Bに属している事象Bvを用意し,それらをUnion-Find木で管理.aとbが異なる集合に属しているという情報が来れば,AaとBb,AbとBaを統合する.
クエリへの解答は,AaとAbが同じ集合に属しているのならaとbは同じ集合に属し,AaとBbが同じ集合に属しているならばaとbは違う集合に属す.どちらでもない場合は,その時点で判断ができない.
struct UnionFind{ vector<int> parent, rank; UnionFind(int n) : parent(n, -1), rank(n, 0) { } int find(int x){ if(parent[x] == -1) return x; else return (parent[x] = find(parent[x])); } bool unite(int x, int y){ x = find(x); y = find(y); if(x == y) return false; if(rank[x] < rank[y]) parent[x] = y; else parent[y] = x; if(rank[x] == rank[y]) rank[x]++; return true; } bool same(int x, int y){ return find(x) == find(y); } }; int N, M; UnionFind uf(100010*2); int main(){ int T; scanf("%d", &T); for(--T; T>=0; --T){ scanf("%d%d", &N, &M); fill(ALL(uf.parent), -1); fill(ALL(uf.rank), 0); for(int i = 0; i < M; ++i){ char str[16]; int a, b; scanf("%s%d%d", str, &a, &b); if(str[0] == 'D'){ uf.unite(a * 2, b * 2 + 1); uf.unite(a * 2 + 1, b * 2); } else{ if(uf.same(a * 2, b * 2)){ printf("In the same gang.\n"); } else if(uf.same(a * 2, b * 2 + 1)){ printf("In different gangs.\n"); } else{ printf("Not sure yet.\n"); } } } } return 0; }