백준 20955 - 민서의 응급 수술

Minjae An·2023년 8월 18일

ps 분리집합 유니온 파인드

PS

목록 보기

39/148

문제

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

리뷰

유니온 파인드를 이용하여 풀이할 수 있는 문제였다. 입력으로 들어오는 두 정점을
유니온 연산으로 하나의 집합으로 형성해주고, 만약 두 정점이 같은 루트내에 이미
속해있는 경우 사이클이 존재하는 것이기 때문에 연산 횟수를 증가시킨다.
이후, parent 배열에서 루트의 개수를 카운팅해준뒤 1을 빼주면 답을 도출할
수 있다. ( $N$ 개의 정점을 연결하는 최소 간선 개수는 $N-1$ 개이기 때문에)

로직의 시간복잡도는 $O(Ma(N))$ 으로 수렴하고 이는 최악의 경우에도 주어진
제한 조건을 무난히 통과한다.

코드

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

import static java.lang.Integer.*;

public class Main {
    static int[] parent;

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

        int N = parseInt(st.nextToken());
        int M = parseInt(st.nextToken());

        parent = new int[N + 1];


        Arrays.fill(parent, -1);

        int count = 0;
        while (M-- > 0) {
            st = new StringTokenizer(br.readLine());
            int u = parseInt(st.nextToken());
            int v = parseInt(st.nextToken());

            int r1 = find(u);
            int r2 = find(v);

            if (r1 == r2) {
                count++;
                continue;
            }

            union(r1, r2);
        }

        int group = 0;
        for (int i = 1; i < parent.length; i++) {
            if (parent[i] < 0)
                group++;
        }

        System.out.print(count + group - 1);
        br.close();
    }

    static void union(int r1, int r2) {
        if (parent[r1] < parent[r2]) {
            parent[r1] += parent[r2];
            parent[r2] = r1;

        } else {
            parent[r2] += parent[r1];
            parent[r1] = r2;
        }
    }

    static int find(int u) {
        if (parent[u] < 0) return u;

        return parent[u] = find(parent[u]);
    }
}