백준 20040번 : 사이클 게임 java

이 문제는 분리 집합을 이용하여 푸는 문제입니다.

첫 번 째 줄에서 N과 M을 받은 후 N개의 정점에서 M개의 선을 이을 때 사이클이 생기지 않으면 0을 출력하고 사이클이 생기면 사이클이 생겼을 때 입력받은 간선의 수를 출력하는 문제입니다.

예제 1번은 모든 간선을 이어도 아래와 같이 사이클이 없으므로 0을 출력합니다.

하지만 예제 2번은 중간에 사이클이 생깁니다.

언제 사이클이 생기는지 보여드리겠습니다.

첫 번째 간선을 입력받았을 때 다음과 같은 모습입니다.

두번째 입력을 받았을 때 위와 같은 모습입니다.

세번째 입력을 받았을 때 다음과 같은 모습입니다.

그리고 네번째 입력을 받을 때 사이클이 생깁니다.

따라서 4를 출력합니다.

이 문제를 풀면서 그래프가 생기는가 생기지 않는가는 union-find 함수를 이용해서 해결해야 합니다.

find 함수는 자신과 연결되어 있는지, 즉 parent 배열을 이용하여 자신의 root 노드를 가져오는 역할을 합니다.

그리고 union 함수는 연결되어 있지 않다면 두 트리를 연결하는 역할을 합니다.

이 두 함수를 유의하시면서 코드를 보시면 되겠습니다.

---

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

public class Main {
    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());

        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());

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

        int count = 0;
        boolean flag = true;
        for(int i = 0; i<M; i++){
            st = new StringTokenizer(br.readLine());

            if(flag) {
                int A = Integer.parseInt(st.nextToken());
                int B = Integer.parseInt(st.nextToken());

                boolean unioned = union(A, B);

                if (!unioned) {
                    count = i + 1;
                    flag = false;
                }
            }
        }

        System.out.println(count);
    }
    static int find(int idx){
        if(parent[idx] == idx)
            return idx;
        else
            return find(parent[idx]);
    }
    static boolean union(int idx1, int idx2){
        int p1 = find(idx1);
        int p2 = find(idx2);

        if(p1 == p2)
            return false;
        else{
            parent[p2] = p1;
            return true;
        }
    }
}