유니온 파인드

Union 연산 : 각 노드가 속한 집합을 1개로 합치는 연산
find 연산 : 특정 노드 a에 관해 a가 속한 집합의 대표 노드를 반환하는 연산

1. 1번과 2번을 연결하고 둘 중 작은 노드번호를 대표값으로 설정
2. 노드번호와 부모노드가 다르면 부모노드의 값을 찾아가 노드번호 검색
3. 1-2번을 반복하다가 노드번호와 부모노드가 같으면 노드번호 출력

문제

https://www.acmicpc.net/problem/1717

해설

union연산:
1. a와 b 대표 노드 찾기
2. 두 원소의 대표 노드끼리 연결하기

find 연산 :
1. a가 대표 노드면 리턴
2.아니면 a의 대표 노드 값을 java find([parent[a]) 값으로 저장 -.> 재귀 함수형태)

checkSame 연산 :
1. a와 b의 대표 노드 찾기
2. 두 대표 노드가 같으면 true
3. 아니면 false return

내코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class B1717 {
	static int[] arr;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());
		
		arr = new int[n+1];
		
		for (int i = 1; i < arr.length; i++) {
			arr[i]=i;
			
		}
		
		for (int i = 0; i < m; i++) {
			st = new StringTokenizer(br.readLine());
			int uf = Integer.parseInt(st.nextToken());
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			
			if(uf==0) {
				union(a,b);
			}
			else {
				if(checkSame(a,b)) {
					System.out.println("YES");
				}
				else
				{
					System.out.println("NO");
				}
			}	
		}	
	}

	private static boolean checkSame(int a, int b) {
		a=find(a);
		b=find(b);
		if(a==b) {
			return true;
		}
		return false;
	}

	private static int find(int a) {
		if(a==arr[a])
			return a;
		else {
			return arr[a] =find(arr[a]);
		}
		
	}

	private static void union(int a, int b) {
		a=find(a);
		b=find(b);
		if(a<b) {
			arr[b]=a;
		}
		else {
			arr[a]=b;
		}
}
}