(코테) 백준_1717_집합의 표현 *유니온 파인드

 

package test;
import java.util.*;
import java.io.*;

public class Backjun_1717Test {
	static int N,M;
	static int[] parents ;
	
	public static void main(String[] args) throws IOException{
		// TODO Auto-generated method stub
		//	기본 세팅
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st= new StringTokenizer(br.readLine());
		 N = Integer.parseInt(st.nextToken());
		 M = Integer.parseInt(st.nextToken());
		 parents = new int[N+1];
		// parents 1로 기본 세잍
		 for(int i =0;i<N+1;i++) {
			 parents[i] = i;			 
		 }
		StringBuilder sb = new StringBuilder();
		for(int i=0;i<M;i++) {
			st= new StringTokenizer(br.readLine());
			
			int input = Integer.parseInt(st.nextToken()); 			
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			if(input==0) {  //0이면 합치기
				union(a,b);
			}else{ //1이면 체크 후 yes no 처리
					//찾아서 최상위 부모 같은지 확인.
					if(find(a)==find(b)) {
						sb.append("YES\n");
				
					}else {
						sb.append("NO\n");

					}
				}					
		}
		System.out.println(sb);
		
	}
	public static int find(int num) {
		//최상위 부모 찾기
			if(parents[num]==num) return parents[num]; //자기가 최상위 루트면 자기값 반환
			
			return parents[num] = find(parents[num]); // 자기 값이 아니다? 그럼 최상위 부모 찾는 재귀 함수 자기가 최상위 부모다? 그럼 그 값 리턴	
		
		
		
	}

	public static void union(int x, int y) {
		int a = find(x);  //루트
		int b = find(y);  //루트
		
		 // if() {} //값 체크 해야하나??? 다 해주면 되나 헷갈리네
		if(a!=b) {
		parents[b] = a;  //최상위 부모로 합치기 		
		}
	}
	
	
}