Submission #101916

---

Source Code Expand

import java.io.IOException;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Arrays;

public class Main {
	static class UnionFind {
		final int tree[];

		public UnionFind(int n) {
			this.tree = new int[n];
			Arrays.fill(tree, -1);
		}

		void union(int x, int y) {
			x = root(x);
			y = root(y);
			if(x != y) {
				if(tree[x] > tree[y]) {
					x ^= y; y ^= x; x ^= y;
				}
				tree[x] += tree[y];
				tree[y] = x;
			}
		}

		boolean find(int x, int y) {
			return root(x) == root(y);
		}
		int root(int x) {
			return tree[x] < 0 ? x : (tree[x] = root(tree[x]));
		}
	}

	public static void main(String[] args) {
		int N = nextInt();
		int M = nextInt();
		int K = nextInt();
		int e[][] = new int[M][];
		for(int i = 0; i < M; i++)
			e[i] = new int[]{nextInt()-1, nextInt()-1};

		boolean dt[] = new boolean[M];
		int Q[][] = new int[K][];
		for(int i = 0; i < K; i++) {
			int q = nextInt();
			if(q == 0) {
				Q[i] = new int[]{q, nextInt()-1};
				dt[Q[i][1]] = true;
			} else {
				Q[i] = new int[]{q, nextInt()-1, nextInt()-1};
			}
		}

		UnionFind uf = new UnionFind(N);
		for(int i = 0; i < M; i++)
			if(!dt[i]) {
				uf.union(e[i][0], e[i][1]);
			}

		ArrayList<Boolean> ans = new ArrayList<Boolean>();
		for(int i = K-1; i >= 0; i--) {
			if(Q[i][0] == 0) {
				 uf.union(e[Q[i][1]][0], e[Q[i][1]][1]);
			} else {
				ans.add(uf.find(Q[i][1], Q[i][2]));
			}
		}

		PrintWriter pw = new PrintWriter(System.out);
		for(int i = ans.size()-1; i >= 0; i--)
			pw.println(ans.get(i) ? "YES" : "NO");
		pw.close();
	}

	static int nextInt() {
		int c = 0;
		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 自動生成された catch ブロック
			e.printStackTrace();
		}
		return -1;
	}
}

Submission Info

Judge Result