백준 20040번
https://www.acmicpc.net/problem/20040

문제

---

생각하기

---

• 그래프에서 사이클을 찾으면 되는 문제이다.

• 유니온 파인드를 통해서 문제 해결이 가능하다.

동작

사이클은 두 노드의 부모가 같으면 사이클이 된다.

            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            
            if (find(a) == find(b)) {
                sb.append(i + 1);
                return sb.toString();
            }

입력 받은 두 노드가 같은 부모가 가지는지 확인하고 아닐 경우 union() 메소드를 실행하면 된다.

결과

코드

---

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

public class Main {

    // input
    private static BufferedReader br;

    // variables
    private static int N, M;
    private static int[] parents, ranks;

    public static void main(String[] args) throws IOException {
        br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        input();

        bw.write(solve());
        bw.close();
    } // End of main()

    private static String solve() throws IOException {
        StringBuilder sb = new StringBuilder();

        for (int i = 0; i < M; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            
            if (find(a) == find(b)) {
                sb.append(i + 1);
                return sb.toString();
            }

            union(a, b);
        }
        
        sb.append(0);
        return sb.toString();
    } // End of solve()

    private static void union(int a, int b) {
        int rootA = find(a);
        int rootB = find(b);

        if (rootA == rootB) return;

        if (ranks[rootA] < ranks[rootB]) {
            // A가 더 부모임
            parents[rootA] = rootB; //  rootA의 부모는 rootB로 변경
        } else {
            // rootA의 높이가 더 높거나 같을 경우
            parents[rootB] = rootA; // rootB의 부모가 rootA가 된다.
            // 이미 A의 높이가 더 높을경우에는 A가 부모가 되고 높이는 증가시키지 않는다.
            if (ranks[rootA] == ranks[rootB]) {
                ranks[rootA]++; // A가 B의 부모가 되어서 rank가 증가한다.
            }
        }
    } // End of union()

    private static int find(int node) {
        if (parents[node] == node) return node;

        return find(parents[node]);
    } // End of find()

    private static void input() throws IOException {
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        parents = new int[N];
        ranks = new int[N];

        for (int i = 1; i < N; i++) {
            parents[i] = i;
        }

    } // End of input()
} // End of Main class