[백준 Gold 4] 20040 사이클 게임 - Java

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

20040번: 사이클 게임

 

접근 과정 : 

• 분리 집합으로 접근하면 간단하다.
• 연결 정보에 따라서 집합으로 합쳐주고. 만약 집합의 번호가 같으면 사이클이 형성된다!!
• 사이클이 형성될 때, i를 리턴한다.

 

+++

비슷한 문제 : https://rays-space.tistory.com/74

[백준 Gold 4] 4803 트리 - Java

20040을 풀고 4803을 풀면 사이클 문제는 익숙해지지 않을까싶다.

 

소스 코드 및 결과 :

package BOJ;

/* 
    사이클 게임
*/

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

public class BOJ20040 {

    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());

        setRoot(n);

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

            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());

            a = findRoot(a);
            b = findRoot(b);
            if (a == b) {
                System.out.println(i);
                return;
            }
            root[b] = a;
        }

        System.out.println(0);

    }

    static int[] root;

    static void setRoot(int n) {
        root = new int[n];

        for (int i = 0; i < n; i++) {
            root[i] = i;
        }
    }

    static int findRoot(int x) {
        if (root[x] == x) {
            return x;
        }

        return root[x] = findRoot(root[x]);
    }

}

 

P.S 

개인적으로 입력의 중간에 결과가 나왔다고 리턴하는 것을 좋아하지 않는다..

그런데 해당 문제에서는 그렇게 해야 속도가 좀 빠르게 나오더라..