[백준 20040] 사이클 게임(Java)

문제 링크 : https://www.acmicpc.net/problem/20040

이 문제는 유니온 파인드를 이용하여 풀 수 있습니다. 유니온 파인드 알고리즘 특성상 사이클 유무를 파악할 수 있기 때문에 유니온 파인드로 각 노드들을 병합하여 사이클이 완성될 때의 반복문 루프 횟수를 출력합니다.

코드는 아래와 같습니다.

import java.util.*;
import java.io.*;

class Main{
    static int N,M,res=0;
    static int[] parent;

    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        parent = new int[N];
        for(int i=0;i<N;i++) parent[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());
            union(a,b,i+1);
            if(res != 0) break;
        }

        System.out.println(res);
    }

    static void union(int a, int b, int idx){
        a = find(a);
        b = find(b);
        if(a != b) parent[b] = a;
        else res = idx;
    }

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