[백준][Java] 28118 - 안전한 건설 계획

1. 문제정보

https://www.acmicpc.net/problem/28118
난이도 : G4
유형 : 분리 집합

---

2. 문제풀이

문제 조건 "서로 다른 두 기둥을 연결하는 빔이 항상 존재하도록 보강 작업을 진행할 수 있음이 보장된다."을 통해 a 작업은 발생할 수 없음을 알 수 있다.
서로 빔으로 연결된 기둥들을 한 개의 기둥으로 변환하여 이렇게 변환된 기둥들을 서로 연결되도록 간선을 이어주면 된다.
서로 이어진 기둥들의 집단 개수 - 1 = 간선 수(정답)

---

3. 코드

uion by rank 기법을 사용하였지만 기본 disjoint set을 사용해도 무방

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

public class Main {

    public static final BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    public static final StringBuilder sb = new StringBuilder();
    public static StringTokenizer st;

    private int N;
    private int M;
    private int[] ranks;
    private int res;

    private int find(int x) {

        if (ranks[x] < 0) {
            return x;
        }
        return ranks[x] = find(ranks[x]);
    }

    private void union(int x, int y) {

        x = find(x);
        y = find(y);

        if (x == y) {
            return;
        }

        if (x < y) {
            ranks[x] += ranks[y];
            ranks[y] = x;
        } else {
            ranks[y] += ranks[x];
            ranks[x] = y;
        }
    }

    private void solution() throws IOException {

        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        ranks = new int[N + 1];
        Arrays.fill(ranks, -1);

        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());

            union(a, b);
        }

        for (int i = 1; i <= N; i++) {
            if (ranks[i] < 0) {
                res++;
            }
        }

        System.out.println(res - 1);
    }

    public static void main(String[] args) throws IOException {

        Main main = new Main();
        main.solution();
    }
}