시간 제한 : 2초, 난이도 : 골드 4, 백준 : 1717번

유니온 파인드 : 일반적으로 여러 노드가 있을 때 특정 2개의 노드를 연결해 1개의 집합으로 묶는 union연산과 두 노드가 같은 집합에 속해 있는지를 확인하는 find연산으로 구성되어 있는 알고리즘이다.

• union 연산 : 2개의 노드를 선택해 각각의 대표 노드를 찾아 연결하는 연산
• find 연산 : 자신이 속한 집합의 대표 노드를 찾는 연산 → 그래프를 정돈하고 시간 복잡도를 향상 시킨다.
  • 대상 노드 배열에 index값과 value값이 동일한지 확인합니다.
  • 동일하지 않으면 value값이 가리키는 index 위치로 이동합니다.
  • 이동 위치의 index값과 value값이 같을 때까지 1-2를 반복합니다. 반복이므로 이 부분은 재귀 함수로 구현합니다.
  • 대표 노드에 도달하면 재귀 함수를 빠져나오면서 거치는 모든 노드 값을 루트 노드 값으로 변경합니다.

import java.util.Scanner;
public class Practice50 {
	public static int[] parent;
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int N = sc.nextInt();
		int M = sc.nextInt();
		
		parent = new int[N + 1];
		for(int i = 0; i <= N; i++) {
			parent[i] = i;
		}
		for(int i = 0;i < M; i++) {
			int question = sc.nextInt();
			int a = sc.nextInt();
			int b = sc.nextInt();
			if(question == 0) {// 0, a, b이면 a가 속한 집합과 b가 속한 집합을 합친다.
				union(a, b);
			}else {
				if(checkSame(a, b)) {
					System.out.println("YES");
				}else {
					System.out.println("NO");
				}
			}
		}
		sc.close();
	}
	public static void union(int a, int b) {
		a = find(a);
		b = find(b);
		if(a != b) {
			parent[b] = a;
		}
	}
	public static int find(int a) {
		if(a == parent[a])
			return a;
		else
			return parent[a] = find(parent[a]);
	}
	public static boolean checkSame(int a, int b) {
		a = find(a);
		b = find(b);
		if(a == b) {
			return true;
		}
		return false;
	}

}