ARC 036 D: 偶数メートル
解法
0〜N-1と、N〜2N-1の2N個の街があると仮定する。
- ノード数2NのUnion-FInd木を用意する。
- xとyの間に敷設する道路の長さが偶数なら、xとy、x+Nとy+Nをuniteする。
- 奇数ならxとy+N、x+Nとyをuniteする。
上記の手順によって、0〜N-1とN〜2N-1の各集合の内部は偶数長の道路で結ばれていて、集合間は奇数長の道路で結ばれていることになる。0〜N-1からN〜2N-1を経由して0〜N-1に戻ってくる事が可能な場合、奇数長の道路を必ず偶数回通るので、偶数メートルで移動が可能であると言える。
コード
import java.io.IOException; public class Main { public static void main(String[] args) { int N = nextInt(); int Q = nextInt(); UnionFind uf = new UnionFind(N * 2); for (int query = 0; query < Q; query++) { int w = nextInt(); int x = nextInt() - 1; int y = nextInt() - 1; int z = nextInt() % 2; if (w == 1) { // 道路を追加 if (z == 0) { uf.unite(x, y); uf.unite(N + x, N + y); } else { uf.unite(x, y + N); uf.unite(x + N, y); } } else { if (uf.isSame(x, y)) { System.out.println("YES"); } else { System.out.println("NO"); } } } } static int nextInt() { int c; try { c = System.in.read(); while (c != '-' && (c < '0' || c > '9')) c = System.in.read(); if (c == '-') return -nextInt(); int res = 0; while (c >= '0' && c <= '9') { res = res * 10 + c - '0'; c = System.in.read(); } return res; } catch (IOException e) { // TODO Auto-generated catch block e.printStackTrace(); } return -1; } } class UnionFind { int[] parts; UnionFind(int n) { parts = new int[n]; for (int i = 0; i < n; i++) parts[i] = i; } public int find(int x) { if (parts[x] == x) return x; return parts[x] = find(parts[x]); } public Boolean isSame(int x, int y) { return find(x) == find(y); } public void unite(int x, int y) { if (find(x) == find(y)) return; parts[find(x)] = find(y); } }