백준 20040 Java 풀이

[20040-사이클 게임]

문제

• 입력으로 점 N개와 (0 ... N - 1) 임의의 점을 잇는 선분 M개가 주어진다.
• 몇번째 선분에서 사이클이 생기는지 출력하는 문제, 사이클이 생성되지 않으면 0을 반환한다.

풀이

• 간단한 Union Find 문제다. 선분을 잇는다 = 합집합 연산 즉, 같은 루트 노드를 바라보도록 만들어 주면서 이미 루트노드가 같다면 같은 집합에 있는 점을 잇는다면 사이클이 형성될 것이다.
  

• 위의 간단한 트리를 보면 같은 루트 노드 (1)을 바라보고 있는 노드들은 어디로 선분을 잇든 사이클이 형성된다. 즉 union을 하기 전 이미 부모 노드가 같다면 해당 순서를 반환하면 된다.

코드

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


public class Main {
    private static int[] parents;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int result = 0;

        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());

        parents = new int[n];

        for (int i = 0; i < n; i++) {
            parents[i] = i;
        }

        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());

            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());

            if (find(a) == find(b)) {
                result = i + 1;
                break;
            }

            union(a, b);
        }

        System.out.println(result);
    }

    private static void union(int a, int b) {
        int rootA = find(a);
        int rootB = find(b);

        parents[rootB] = rootA;
    }

    private static int find(int n) {
        if (parents[n] == n) {
            return n;
        }
        return parents[n] = find(parents[n]);
    }
}