BOJ_20040_사이클게임_java

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

20040번: 사이클 게임

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

/**
 백준 20040번 사이클게임
 골드 4
 */
public class BOJ_20040_사이클게임 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        int[] arr = new int[n]; // 연결 부모 확인용 배열
        for (int i = 0; i<n; i++){ // 초기화
            arr[i] = i;
        }
        for (int i = 1; i<=m; i++){
            st = new StringTokenizer(br.readLine());
            int n1 = Integer.parseInt(st.nextToken());
            int n2 = Integer.parseInt(st.nextToken());
            if (union(n1, n2, arr)){
                System.out.println(i);
                return;
            }
//            System.out.println(Arrays.toString(arr)); // 테스트용
        }
        System.out.println(0);
    }

    public static int find(int x, int[] arr){ // 자신의 최신 부모 찾기
        if (arr[x] == x){
            return x;
        }else{
            return arr[x] = find(arr[x], arr);
        }
    }

    public static boolean union(int a, int b, int[] arr){ // 합치기
        a = find(a, arr);
        b = find(b, arr);
        if (a==b) return true; // 처음 진입시 같은 경우 사이클로 판정
        arr[b] = a;
        return false;
    }
}