[Algorithm] C++ 백준 25172번: 꼼꼼한 쿠기의 졸업여행

정점이 하나씩 영구적으로 삭제되는 과정마다, 남아있는 정점이 1개 이상 존재하고 그래프가 **연결(모든 정점 쌍이 도달 가능)**인지 빠르게 판별해야 한다.
삭제는 DSU로 직접 처리하기 까다로우므로, 삭제 순서를 역순으로 뒤집어 “추가” 문제로 바꾸는 오프라인 풀이가 핵심이다.

문제 정보

문제 링크: https://www.acmicpc.net/problem/25172

문제 요약:

\(N\)개의 관광지(정점)와 \(M\)개의 길(무방향 간선)로 이루어진 그래프가 주어진다.
이후 정점이 \(N\)번에 걸쳐 하나씩 삭제되며, 삭제되는 정점과 연결된 모든 간선도 함께 사라진다(영구 삭제).
각 시점(처음 포함)마다, 남은 정점이 비어있지 않고 그래프가 연결이면 CONNECT, 아니면 DISCONNECT를 출력한다.

제한 조건:

시간 제한: 2초
메모리 제한: 512MB
\(1 \le N \le 200,000\)
\(1 \le M \le 200,000\)

입출력 예제

입력 1:

출력 1:

1
2
3
4
5
6
CONNECT
DISCONNECT
CONNECT
CONNECT
CONNECT
DISCONNECT

접근 방식

핵심 관찰 1: “삭제”를 “추가”로 바꾸면 DSU로 처리 가능

정점 삭제는 DSU가 지원하지 않지만, 삭제 순서를 역순으로 보면 정점이 하나씩 추가되는 과정이 된다.

원래 문제: \(v_1, v_2, \ldots, v_N\) 순서로 정점 삭제
역순 문제: \(v_N, v_{N-1}, \ldots, v_1\) 순서로 정점 추가
- 정점 \(v\)를 추가할 때, 이미 활성화(active)된 이웃과만 간선을 “복원”해 DSU로 합친다.

핵심 관찰 2: 연결 여부는 “활성 컴포넌트 수”로 판정

각 시점에서

활성 정점 수가 0이면 무조건 DISCONNECT
활성 정점 수가 1 이상이고, 활성 컴포넌트 수가 정확히 1이면 CONNECT

정점 \(v\)를 새로 활성화하면 컴포넌트가 1 증가하고, 활성 이웃과 DSU로 합칠 때마다(서로 다른 컴포넌트였다면) 컴포넌트 수가 1 감소한다.

알고리즘 설계 (Mermaid Flowchart)

flowchart TD
    A["입력: N, M, 간선 목록, 삭제 순서 v[1..N]"] --> B["활성 배열 active 초기화 (모두 false)"]
    B --> C["DSU 초기화, activeCnt=0, comps=0"]
    C --> D["i = N..1 (역순)"]
    D --> E["v = v[i] 를 활성화"]
    E --> F["activeCnt += 1, comps += 1"]
    F --> G["v의 모든 이웃 u에 대해, active[u]면 DSU.union(v,u)"]
    G --> H["union 성공 시 comps -= 1"]
    H --> I{"activeCnt > 0 && comps == 1 ?"}
    I -- "yes" --> J["ok[t] = CONNECT 저장"]
    I -- "no" --> K["ok[t] = DISCONNECT 저장"]
    J --> L["다음 i"]
    K --> L
    L --> M["정방향 출력: k번 삭제 상태 = 역순에서 (N-k)개 추가 상태"]

단계별 로직

입력 파싱: 인접 리스트로 그래프 저장, 삭제 순서 배열 저장
역순 처리:
- 정점을 하나 활성화하고(activeCnt++, comps++)
- 활성 이웃과 DSU union하여 컴포넌트 수 감소
- activeCnt>0 && comps==1이면 그 시점은 연결
정방향 매핑:
- 정방향에서 \(k\)개 삭제한 상태 ↔ 역순에서 \(N-k\)개 추가한 상태
- \(k=0..N\)에 대해 정답 출력(총 \(N+1\)줄)

복잡도 분석

항목	복잡도	비고
시간 복잡도	\(O((N+M)\alpha(N))\)	각 간선은 양 끝이 활성화될 때 최대 1번 union 시도
공간 복잡도	\(O(N+M)\)	인접 리스트 + DSU + 활성 배열

코너 케이스 및 실수 포인트

케이스	설명	처리 방법
모든 정점 삭제 후	정점이 0개면 연결 개념 성립 불가	`activeCnt==0`이면 무조건 `DISCONNECT`
처음부터 비연결	초기 그래프가 이미 여러 컴포넌트	역순 처리 후 `ok[N]`가 false가 될 수 있음
간선이 없는 그래프	\(M=0\)	정점 1개일 때만 `CONNECT`, 그 외 `DISCONNECT`
중복 union	같은 컴포넌트끼리 합치기 시도	union 성공 여부로 `comps` 감소 여부 결정
출력 줄 수	처음 상태 + N번 삭제 결과	총 \(N+1\)줄 출력

구현 코드 (C++)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
// 42jerrykim.github.io에서 더 많은 정보를 확인 할 수 있다
#include <bits/stdc++.h>
using namespace std;

struct DSU {
    vector<int> p, sz;
    DSU(int n = 0) { init(n); }
    void init(int n) {
        p.resize(n + 1);
        sz.assign(n + 1, 1);
        iota(p.begin(), p.end(), 0);
    }
    int find(int x) {
        while (p[x] != x) {
            p[x] = p[p[x]];
            x = p[x];
        }
        return x;
    }
    bool unite(int a, int b) {
        a = find(a); b = find(b);
        if (a == b) return false;
        if (sz[a] < sz[b]) swap(a, b);
        p[b] = a;
        sz[a] += sz[b];
        return true;
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, M;
    cin >> N >> M;

    vector<vector<int>> adj(N + 1);
    for (int i = 0; i < M; i++) {
        int a, b;
        cin >> a >> b;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }

    vector<int> del(N + 1);
    for (int i = 1; i <= N; i++) cin >> del[i];

    DSU dsu(N);
    vector<char> active(N + 1, 0);

    long long activeCnt = 0;
    long long comps = 0;

    // ok[t] = reverse process after adding t vertices
    vector<char> ok(N + 1, 0);

    int t = 0;
    for (int i = N; i >= 1; i--) {
        int v = del[i];
        active[v] = 1;
        activeCnt++;
        comps++; // new vertex introduces one new component

        for (int u : adj[v]) {
            if (active[u]) {
                if (dsu.unite(v, u)) comps--;
            }
        }

        t++;
        ok[t] = (activeCnt > 0 && comps == 1);
    }

    // forward state after k deletions == reverse state after (N-k) additions
    for (int k = 0; k <= N; k++) {
        int added = N - k;
        cout << (ok[added] ? "CONNECT" : "DISCONNECT") << "\n";
    }

    return 0;
}