boj 20040 사이클 게임

문제 링크

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

문제 풀이

이 문제는 유니온 파인드를 이용하여 풀었다.
사이클이 존재할려면 각 부모가 같으면 존재한다.
존재하지 않는다면 각 노드를 union 시킨다.

부모찾기 find 함수

private static int find(int x) {
        if(parent[x]==x) return x;
        else return find(parent[x]);
    }

union 함수

private static void union(int x, int y) {
        x = find(x);
        y = find(y);
        if (x <= y) {
            parent[y]=x;
        }else {
            parent[x]=y;
        }
    }

전체 코드

package BOJ;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
//boj 20040
public class 사이클게임 {

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

        for (int i = 0; i < n; i++) {
            parent[i]=i;
        }
        int anw = 0;
        int cnt = 0;
        boolean flag = false;
        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());

            cnt++;
            //부모가 다르면
            if(find(a)!=find(b)){
                //union
                union(a,b);
            }
            //부모가 같으면 사이클
            else {
                flag= true;
                anw=cnt;
                break;
            }

        }
        if(flag) System.out.println(anw);
        else System.out.println(0);

    }

    private static void union(int x, int y) {
        x = find(x);
        y = find(y);
        if (x <= y) {
            parent[y]=x;
        }else {
            parent[x]=y;
        }
    }

    private static int find(int x) {
        if(parent[x]==x) return x;
        else return find(parent[x]);
    }
}