swea 3289 서로소 집합

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWBJKA6qr2oDFAWr 

SW Expert Academy

 

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Solution_3289_유동훈 {
	
	static int[] parents;
	static int N,M;
	
	/**
	 * 크기가 1인 서로조 집합 생성
	 * 모든 노드가 자신을 부모로 하는 집합으로 만들기
	 */
	static void make()
	{
		parents=new int[N+1];
		for(int i=0;i<=N;++i)
		{
			parents[i]=i;
		}
	}
	
	/**
	 * x의 대표자 찾기
	 * @param x
	 * @return
	 */
	public static int find(int x) {
		//x의 부모== x->내가 루트임.
		if (parents[x] == x) 
		{
			return x;
		}
		//아니면 내 부모의 부모를 찾아라
		//반복
		//else 
		{
			return parents[x]=find(parents[x]);
			//우리의 대표자를 나의 부모로 : path compression
		}
	}
 
	/**
	 * 
	 * @param a
	 * @param b
	 * (A를 B에 연결)
	 * A의 루트노드를 B의 루트노드에 연결
	 * (A위에 B를 부모로)
	 * 
	 * @return 유니언 성공시 true
	 */
	public static boolean union(int a, int b) {
		int rootA = find(a);
		int rootB = find(b);
 
		if (rootA == rootB) return false;
		
		//B의 루트노드를 A의 루트노드에 연결
		parents[rootA] = rootB;
		return true;
	}

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		int T=Integer.parseInt(br.readLine());
		
		for(int t=1;t<=T;++t)
		{
			StringTokenizer st=new StringTokenizer(br.readLine());
			N=Integer.parseInt(st.nextToken());	//정점수
			M=Integer.parseInt(st.nextToken());	//간선수
			
			//edgeList=new Edge[E];
			
			StringBuilder sb= new StringBuilder();
			sb.append("#").append(t).append(" ");
			
			make();	//서로소 집합으로 초기화
			
			for(int i=0;i<M;++i)
			{
				st= new StringTokenizer(br.readLine());
				
				int command=Integer.parseInt(st.nextToken());
				//합집합
				if(command==0)
				{
					union(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));
				}
				else if(command==1)
				{
					if(find(Integer.parseInt(st.nextToken()))==find(Integer.parseInt(st.nextToken())))
						sb.append("1");
					else
						sb.append("0");
				}
				
			}
			//입력끝!
			sb.append("\n");
			
			bw.write(sb.toString());
			
			
		}
		bw.flush();
		bw.close();
		

	}

}