[백준] 20040. 사이클 게임

문제 링크

[백준] 20040. 사이클 게임

풀이 과정

간선을 이루는 두 정점이 입력으로 주어지고, 사이클을 판단해야 한다는 문제의 조건에서 크루스칼 알고리즘을 떠올렸습니다. 크루스칼 알고리즘 내부에서 Union-find 알고리즘으로 사이클의 발생 유무를 알 수 있기에, 문제 풀이에 적합하다고 생각해 구현했습니다.

코드

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

public class Main {
    static int n, m;
    static int[] parent;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = stoi(st.nextToken());
        m = stoi(st.nextToken());
        parent = new int[n];

        for (int i = 0; i < n; i++) parent[i] = i;

        for (int i = 1; i <= m; i++) {
            st = new StringTokenizer(br.readLine());
            int a = stoi(st.nextToken());
            int b = stoi(st.nextToken());

            int pa = find(a);
            int pb = find(b);

            if (pa == pb) {
                System.out.println(i);
                System.exit(0);
            }

            union(pa, pb);
        }

        System.out.println(0);
    }

    static int find(int x) {
        if (x == parent[x]) return x;
        return find(parent[x]);
    }

    static void union(int x, int y) {
        if (x < y) parent[y] = x;
        else parent[x] = y;
    }

    static int stoi(String s) {
        return Integer.parseInt(s);
    }
}