백준 1717번 : 집합의 표현

 문제

www.acmicpc.net/problem/1717

1717번: 집합의 표현

1717 집합의 표현

 

 구현 방법

 union-find 알고리즘을 통해 구현하였습니다.

n만큼 집합을 생성하고 연산을 받아 0 a b이면 합집합으로 union(a, b) 를 통해 집합을 합쳐줍니다.

1 a b면 연결 되었는지 확인해야합니다. path competition을 통해 연산 시 부모를 루트 노드로 향하게 구현하였으므로 a의 부모, b의 부모를 찾아 같으면 연결 -> "YES" 출력, 다르면 비연결 -> "NO"를 출력해줍니다.

 

 구현 코드

package BOJ.Gold;

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

public class B1717_집합의표현 {
	static int N, M;
	static int[] parents, rank;
	static void makeSet() {
		for (int i=0;i<=N;i++) {
			parents[i] = -1;
			rank[i] = 0;
		}
	}
	
	static int findSet(int x) {
		if (parents[x]<0) return x;
		return parents[x] = findSet(parents[x]);
	}
	
	static void union(int a, int b) {
		int aRoot = findSet(a);
		int bRoot = findSet(b);
		if (aRoot==bRoot) return;
		if (rank[aRoot]<rank[bRoot]) parents[aRoot] = bRoot;
		else parents[bRoot] = aRoot;
		
		if (rank[aRoot]==rank[bRoot]) rank[aRoot]++;
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		StringTokenizer st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		parents = new int[N+1];
		rank = new int[N+1];
		makeSet();
		for (int i=0;i<M;i++) {
			st = new StringTokenizer(br.readLine());
			int menu = Integer.parseInt(st.nextToken());
			int from = Integer.parseInt(st.nextToken());
			int to = Integer.parseInt(st.nextToken());
			if (menu==0) union(from, to); // 0일 때 합치기
			else { // 1일 때 연결 확인
				if (findSet(from)==findSet(to)) sb.append("YES\n"); // 부모가 같으면 연결
				else sb.append("NO\n"); // 부모가 다르면 비연결
			}
		}
		System.out.println(sb);
	}
}

 

정답!