백준(BOJ) 20040: 사이클 게임

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

자료구조 문제로 Union-find집합자료구조를 묻고 있다.

"사이클=집합" 이라는 것을 항상 기억하고 사이클에 관한 문제라면 어떻게든 Union-find를 사용하려고 해야한다.

사이클은 다른 말로 집합을 형성하는 것이다. 같은 집합에 속해있는 정점들만 선택하면 하나의 사이클을 만든다. 

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

public class Main {
    public static class Edge {
        int from;
        int to;

        public Edge(int from, int to) {
            this.from = from;
            this.to = to;
        }
    }

    public static class Union_find {
        int[] parent;
        int[] size;

        public Union_find(int numOfNodes) {
            parent = new int[numOfNodes];
            for (int i = 0; i < numOfNodes; ++i)
                parent[i] = i;
            size=new int[numOfNodes];
            Arrays.fill(size, 0);
        }

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

        void union(int parentOfX, int parentOfY) {
            if (size[parentOfX] < size[parentOfY]) {
                size[parentOfY] += size[parentOfX];
                size[parentOfX] = 0;
                parent[parentOfX] = parentOfY;
            } else {
                size[parentOfX] += size[parentOfY];
                size[parentOfY] = 0;
                parent[parentOfY] = parentOfX;
            }
        }
    }

    public static void solution(int n, int m, Edge[] edges) {
        Union_find un = new Union_find(n);
        for (int i = 0; i < m; ++i) {
            int parentOfFrom = un.find(edges[i].from);
            int parentOfTo = un.find(edges[i].to);
            if (parentOfFrom != parentOfTo) {
                un.union(parentOfTo, parentOfFrom);
            } else {
                System.out.println(i + 1);
                return;
            }
        }
        System.out.println(0);
    }

    public static void main(String[] args) throws Exception {
        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());
        Edge[] edges = new Edge[m];
        for (int k = 0; k < m; ++k) {
            st = new StringTokenizer(br.readLine());
            int from = Integer.parseInt(st.nextToken());
            int to = Integer.parseInt(st.nextToken());
            edges[k] = new Edge(from, to);
        }
        solution(n, m, edges);

    }
}