[백준] 1717 - 집합의 표현

 

[문제링크]

1717번: 집합의 표현

 

0. parents[i] : i번째 노드 부모 노드를 가리킨다

 

1. init함수 : 자기 자신을 부모로 설정, 즉 원소 1개짜리의 집합을 n+1개 생성한다

 

2. getRoot함수 : 자기 자신이 부모일때까지 부모를 따라간다. 즉, 해당 원소가 속한 집합의 root를 구한다

 

3. mergeGroup함수 : 양 집합의 부모를 구해서, 한쪽의 부모를 상대방으로 변경한다

 

4. isSameGroup : 양 집합의 부모를 비교한다

 

5. init로 초기화 해준 후, 입력값에 맞춰 함수만 부르면 끝

 

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

public class Main {
	public static void main(String[] args)throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		n = pint(st.nextToken());
		m = pint(st.nextToken());
		init();
		int oper,n1,n2;
		for (int i = 0; i < m; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			oper = pint(st.nextToken());
			n1 = pint(st.nextToken());
			n2 = pint(st.nextToken());
			
			if(oper==0) {
				mergeGroup(n1, n2);
			}else {
				sb.append(isSameGroup(n1, n2)).append("\n");
			}
		}System.out.println(sb);
	}
	
	static int[]parents;
	static int n,m;
	
	static void init() {
		parents=new int[n+1];
		for (int i = 0; i < n+1; i++) {
			parents[i]=i;
		}
	}
	
	static int getRoot(int x) {
		if(parents[x]!=x)return parents[x]=getRoot(parents[x]);
		else return x;
	}
	
	static void mergeGroup(int x, int y) {
		parents[getRoot(y)]=getRoot(x);
	}
	
	static String isSameGroup(int x, int y) {
		return getRoot(x)==getRoot(y)?"YES":"NO";
	}
	
	static int pint(String s) {
		return Integer.parseInt(s);
	}
}

결과 화면