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

 

문제 출저 

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

20040번: 사이클 게임

 

 

문제 풀이 

정점의 개수(n)가 주어지고 정점을 잇는 선분(m)이 주어집니다. 

이 때, 사이클이 몇 번째 순서에서 이루어지는지 구하는게 이 문제의 요구 사항입니다.

 

이 문제를 풀기 위해 Union-Find를 도입했습니다. 

선분이 주어지면 각 시작과 끝의 부모를 비교하여 부모가 같으면 사이클이 이루어진거여서 순서를 저장하고 출력합니다.

부모가 같지 않다면 부모를 같게 만들어줍니다. 

이 같은 로직을 m개 반복했을 때 사이클이 형성되지 않는다면 0을 출력합니다. 

 

 

소스 코드

package baekjoon.backjoon9.day07;


/*
사이클 게임
https://www.acmicpc.net/problem/20040
 */

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

public class B20040 {

    static int n, m;

    static int[] parents;


    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());

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

        StringBuilder sb = new StringBuilder();
        boolean flag = false;

        for (int i = 1; i <= m; i++) {
            st = new StringTokenizer(br.readLine());
            int s = Integer.parseInt(st.nextToken());
            int e = Integer.parseInt(st.nextToken());

            if(find(s) == find(e) && !flag) {
                sb.append(i);
                flag = true;
            }
            else {
                union(s, e);
            }
        }

        if (!flag) {
            sb.append(0);
        }

        System.out.println(sb);
    }

    public static int find(int x) {
        if(parents[x] == x) {
            return x;
        }
        else {
            return find(parents[x]);
        }
    }

    public static void union(int x, int y) {
        x = find(x);
        y = find(y);

        if (x != y) {
            if (x > y) {
                parents[x] = y;
            }
            else {
                parents[y] = x;
            }
        }


    }



}