[Java] 백준 20040번. 사이클게임 (골드4)

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

20040번: 사이클 게임

 

또 다른 웰 노운(Well Known인데 우리는 모르는) 알고리즘, 분리집합의 등장입니다. 

유니온이라고도 알려져 있습니다.

유니온은 일종의 단방향 트리라고 생각하셔도 될 것 같습니다.

데이터들을 집합들로 구분할때 어떻게 할 수 있을까요?

일일히 넘버링을 붙이거나 이름을 붙여도 되겠지만, 구현은 어떻게 하실건가요?

두개의 집합이 합쳐질때는요?

 

분리집합은 자신들을 대표하는 데이터를 부모로 가리킴으로서 자신이 속한 집합을 구분합니다.

 

이 데이터를 노드라고 생각한다면, 집합은 여러 노드들이 연결된 그래프가 되겠죠.

자신이 이미 속한 집합의 노드와 연결된다면 그 그래프는 사이클이 생긴 그래프가 됩니다.

간단하죠?

 

 

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

public class Main {
	static StringTokenizer st;
	static int[] parent;

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		int answer = 0;
		st = new StringTokenizer(br.readLine());
		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());

		parent = new int[N];
		for (int n = 0; n < N; n++) {
			parent[n] = n;
		}

		for (int m = 1; m <= M; m++) {
			st = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			int aParent = findParent(a);
			int bParent = findParent(b);

			if (aParent == bParent) {
				answer = m;
				break;
			} else {
				parent[aParent] = bParent;
			}
		}

		System.out.println(answer);
	}

	static int findParent(int a) {
		if (parent[a] == a) {
			return a;
		} else {
			parent[a] = findParent(parent[a]);
			return parent[a];
		}
	}
}