백준 20040 - 사이클 게임 (자바 JAVA)

 

 

유니온파인드로 풀었습니다. 

상세 풀이방법은 아래 코드 및 주석 내용을 보면 이해가 되실겁니다. 

 

 

 

import java.io.*;
import java.util.*;
 
public class cycleGame {
 
    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;
 
        st = new StringTokenizer(br.readLine());
 
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
 
        parent = new int[N+1];
 
        for(int i=1; i<=N; i++){
            parent[i] = i; // 유니온파인드 배열 초기화
        }
 
        for(int i=1; i<=M; i++){
            // 데이터 입력
            st = new StringTokenizer(br.readLine());
            int from = Integer.parseInt(st.nextToken());
            int to = Integer.parseInt(st.nextToken());
 
            // 판별 알고리즘
            if (isUnion(from,to)) { // 두 지점은 연결되어 있는가?
                System.out.println(i); // 있다면 출력하고 끝낸다
                return;
            }
            else Union(from, to); // 아직 연결되어있지 않다면 연결시켜 준다
        }
 
        System.out.println(0);
 
    }
 
    public static int find(int x){
        if (x == parent[x]) return x;
        return parent[x] = find(parent[x]);
    }
 
    public static boolean isUnion(int x, int y){
        int a = find(x);
        int b = find(y);
        return a==b;
    }
 
    public static void Union(int x, int y){
        int a = find(x);
        int b = find(y);
        if (a<b) parent[b] = a;
        else parent[a] = b;
    }
 
}