단절점과 이중 연결 요소

정의

무방향 연결 그래프에서

• 단절점(cut vertex, articulation point): 그 정점과 거기 붙은 간선을
  제거하면 그래프가 둘 이상으로 쪼개지는 정점.
• 단절선(bridge): 제거하면 그래프가 쪼개지는 간선.

이들은 네트워크의 취약점을 뜻한다. "고장 나면 통신이 끊기는 라우터/회선"이
바로 단절점/단절선이다.

DFS 트리와 low 값

무방향 그래프를 DFS하면 트리 간선과 역방향 간선만 생긴다(교차 간선이
없음). 각 정점에 방문 순서 disc를 매기고, "그 서브트리에서 역방향 간선을 타고
도달할 수 있는 가장 이른(작은 disc) 정점"을 low로 정의한다.

$$ low[u] = \min\Big( disc[u],\ \min_{u\to v \text{ 백간선}} disc[v],\ \min_{u\to c \text{ 트리간선}} low[c] \Big) $$

low는 "이 서브트리가 자기 위쪽 조상으로 몰래 올라갈 수 있는 최선의 높이"를
나타낸다.

단절선 판정

트리 간선 \(u \to v\)(\(v\)는 자식)에 대해

$$ low[v] > disc[u] $$

이면 간선 \((u, v)\)는 단절선이다. 자식 서브트리가 \(u\)를 거치지 않고는
\(u\) 위로 올라갈 길이 전혀 없다는 뜻이기 때문이다. 단, 다중 간선이 있으면
부모로의 역방향을 한 번만 무시하도록 주의해야 한다.

단절점 판정

두 경우로 나뉜다.

• 루트가 아닌 정점 \(u\): 어떤 자식 \(v\)에 대해 \(low[v] \ge disc[u]\)이면 \(u\)는
  단절점. (자식이 \(u\)를 통하지 않고는 위로 못 올라감 → \(u\)를 빼면 자식
  서브트리가 분리됨.)
• DFS 트리의 루트: 자식이 2개 이상이면 단절점.

단절선은 부등호가 >(같으면 안 됨)인 반면 단절점은 >=(같아도 됨)라는 점이
가장 헷갈리는 부분이니 정확히 구분하자.

이중 연결 요소

단절점으로 나뉘지 않는 극대 부분을 이중 연결 요소(BCC) 라 한다. 정확히는
간선 기준으로 묶으며, 단절선 하나로만 이어진 두 덩어리는 서로 다른 BCC다.
모든 BCC를 한 정점으로 줄이면 블록-컷 트리가 되어, 정점 사이의 "반드시
거쳐야 하는 단절점" 구조를 트리로 다룰 수 있다.

복잡도

DFS 한 번으로 모든 disc, low를 계산하므로 \(O(V + E)\)다.

단절점·단절선 동시 판정

부모 간선을 인덱스로 구분해 다중 간선까지 올바로 처리한다.

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 100001;
vector<pair<int,int>> g[MAXN];  // (이웃, 간선번호)
int disc[MAXN], low[MAXN], timer_cnt = 0;
bool is_cut[MAXN];
vector<int> bridges;            // 단절선의 간선 번호

void dfs(int u, int parent_edge) {
    disc[u] = low[u] = ++timer_cnt;
    int child = 0;
    bool cut = false;
    for (auto [v, eid] : g[u]) {
        if (eid == parent_edge) continue;   // 들어온 간선은 무시(다중간선 안전)
        if (disc[v]) {                       // 역방향 간선
            low[u] = min(low[u], disc[v]);
        } else {
            child++;
            dfs(v, eid);
            low[u] = min(low[u], low[v]);
            if (low[v] > disc[u]) bridges.push_back(eid);   // 단절선
            if (parent_edge != -1 && low[v] >= disc[u]) cut = true; // 비루트 단절점
        }
    }
    if (parent_edge == -1 && child >= 2) cut = true;          // 루트 단절점
    is_cut[u] = cut;
}

int main() {
    int n, m; scanf("%d %d", &n, &m);
    for (int i = 0; i < m; i++) {
        int a, b; scanf("%d %d", &a, &b);
        g[a].push_back({b, i});
        g[b].push_back({a, i});
    }
    for (int i = 1; i <= n; i++) if (!disc[i]) dfs(i, -1);
    // is_cut[v] = v가 단절점, bridges = 단절선 간선 번호 목록
    return 0;
}

흔한 실수

• 부등호 혼동 — 단절선은 low[v] > disc[u], 단절점(비루트)은
  low[v] >= disc[u]. 등호 한 글자 차이로 결과가 완전히 달라진다.
• 다중 간선 — 같은 두 정점을 잇는 간선이 둘이면 그 둘은 단절선이 아니다.
  부모로의 간선 번호(정점 번호 아님)로 무시해야 안전하다.
• 루트 특수 처리 — 루트는 low 조건이 아니라 자식 개수로 판정한다.
• 비연결 그래프 — 컴포넌트마다 DFS를 새로 시작해야 한다.

BCC 추출 (간선 스택)

DFS 중 방문한 간선을 스택에 쌓다가, 단절점 조건(low[v] >= disc[u])이 성립하면
스택에서 해당 간선까지 꺼내 하나의 BCC로 묶는다. 이렇게 얻은 BCC들로
블록-컷 트리를 세우면 다음이 가능하다.

단절선이 하나도 없는 그래프는 간선 이중 연결이며, 모든 간선이 어떤 사이클에
속한다. 이 구조는 이후 배울 도미네이터 트리, 그리고 네트워크 신뢰성 문제의
바탕이 된다.