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

문제

---

생각하기

---

✔️ 유니온 파인드

동작

최소 몇번의 연산을 해야하는지를 구해야하는데,

고려해야할 사항이
1. 사이클이 있는가
2. 몇 개의 그룹으로 되어있는가

처음에는 노드들이 모두 다른 노드에 있으면서 다른 부모의 값을 가지고 있으면서 union을 한 후 같은 부모의 값을 가지게 된다.

그런데 find(a) == find(b)라는 얘기는 같은 부모인 상황이므로 사이클이 발생했음을 의미하므로 연결을 끊어내는 연산을 해야한다.

또 하나의 트리로 만들어야 하기 때문에 몇 개의 그룹이 있는지를 파악하고 하나로 합치는 연산을 한다.

만약 2개의 트리라면 합치는데 한번의 연산이 필요하기 때문에 그룹의 개수 - 1의 연산

결과

코드

---

import java.io.*;
import java.util.Arrays;
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();

        int count = 0;
        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)) {
                // 처음 부모가 다른 상태에서 union을 함으로써 부모가 같게 만들었는데,
                // 다시 부모가 같은 경우가 나왔다 == 사이클이 발생하였다.
                // 사이클을 제거하는 횟수 추가
                count++;
            } else {
                // 부모가 다르면 합친다.
                union(a, b);
            }
        }


        // 몇개의 트리로 구성이 되어있는지를 파악
        int group = 0;
        for (int i = 1; i <= N; i++) {
            if (parents[i] == i) group++;
        }

        // 2개의 그룹이 있을 경우 하나의 그룹으로 만드는데 1번의 연산이 필요함
        // 그래서 group개수 - 1의 연산이 필요하다.
        int ans = count + group - 1;
        sb.append(ans);
        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]) {
            parents[rootA] = rootB;
        } else if (ranks[rootA] > ranks[rootB]) {
            // b의 rank가 더 낮으므로, a를 b의 부모로 설정
            parents[rootB] = rootA;
        } else {
            // 두 트리의 높이가 같을 때, 하나를 다른 하나의 부모로 만들고 rank를 증가시킴
            parents[rootB] = rootA;
            ranks[rootA]++;
        }
    } // End of union()

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

        return parents[node] = 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 + 1];
        ranks = new int[N + 1];
        for (int i = 0; i <= N; i++) {
            parents[i] = i;
        }
    } // End of input()
} // End of Main class