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);
	}
}