Submission #420342

---

Source Code Expand

import java.io.*;
import java.util.*;
import java.lang.ArrayIndexOutOfBoundsException;
import java.math.BigInteger;

/**
 * @author yoshikyoto
 */
class Main {
	public static void main(String[] args) throws Exception {
		Scanner sc = new Scanner(new InputStreamReader(System.in));
		int n = sc.nextInt();
		int q = sc.nextInt();
		
		UnionFindTree uft = new UnionFindTree(n);
		
		for (int i = 0; i < q; i++) {
			int p = sc.nextInt();
			int a = sc.nextInt();
			int b = sc.nextInt();
			
			if(p == 0){
				uft.unite(a, b);
			} else {
				if(uft.same(a, b)){
					System.out.println("Yes");
				}else{
					System.out.println("No");
				}
			}
		}
		sc.close();
	}
}

/**
 * UnionFindTree 
 * @author yoshikyoto
 */
class UnionFindTree {
	public int[] parent, rank;
	public int n;
	public int count;

	// 初期化
	UnionFindTree(int n) {
		this.n = n;
		count = n;
		parent = new int[n];
		rank = new int[n];
		for (int i = 0; i < n; i++) {
			parent[i] = i;
			rank[i] = 0;
		}
	}

	// 根を求める
	int find(int x) {
		if (parent[x] == x) {
			return x;
		} else {
			return parent[x] = find(parent[x]);
		}
	}

	// xとyの集合を結合
	void unite(int x, int y) {
		x = find(x);
		y = find(y);
		if (x == y) {
			return;
		}
		if (rank[x] < rank[y]) {
			parent[x] = y;
			count--;
		} else {
			parent[y] = x;
			if (rank[x] == rank[y])
				rank[x]++;
			count--;
		}
	}

	// xとyが同じ集合か
	boolean same(int x, int y) {
		return find(x) == find(y);
	}
}

Submission Info

Judge Result