단절점 (Articulation Point)

2026년 6월 24일 · 수정 2026년 6월 24일 · 📖 약 4분 · 1,300자/단어 #algorithm #graph #articulation-point #dfs

정의

단절점 (Articulation Point, Cut Vertex) 은 무향 연결 그래프에서 제거했을 때 그래프가 둘 이상의 컴포넌트로 분리되는 정점. Robert Tarjan 의 1972년 논문에서 DFS 기반 O(V+E) 알고리즘이 처음 제시되었다.

문제 상황과 동기

네트워크 신뢰성, 도로망, 서버 클러스터 등에서 하나의 장애로 전체가 분리되는 지점 을 찾는 문제.

naive: 정점 하나씩 제거 후 BFS/DFS 로 컴포넌트 개수 확인. O(V · (V+E)). V=10^5 면 불가.
Tarjan: DFS 한 번 (O(V+E)) 에 모든 단절점 탐지.

핵심 통찰: DFS 트리 상에서 어떤 정점 u 의 서브트리에서 u 보다 위로 올라가는 back edge 가 없으면 u 는 단절점. disc[u] (발견 시각) 와 low[u] (서브트리에서 도달 가능한 가장 빠른 시각) 두 배열만으로 판정.

시각화

위 애니메이션은 정점 4 를 제거 시 그래프가 두 컴포넌트 {1,2,3} 과 {5,6,7} 로 분리됨을 보여준다.

핵심 아이디어

DFS 트리를 그리며 각 정점 u 에 대해:

disc[u]: DFS 방문 순서 (발견 시각).
low[u]: u 의 서브트리에서 back edge 로 도달 가능한 가장 빠른 disc 값.

low[u] = min(
    disc[u],
    disc[back edge 타겟들],
    low[자식들]
)

단절점 판정

root (DFS 시작점): 자식이 2개 이상이면 단절점.
non-root u: 어떤 자식 v 에 대해 low[v] >= disc[u] 면 단절점.

왜? v 의 서브트리에서 u 보다 위로 못 올라간다 → u 를 제거하면 v 서브트리 분리.

알고리즘

disc[1..N] = 0, low[1..N] = 0, timer = 0
is_articulation[1..N] = false

dfs(u, parent):
    timer++
    disc[u] = low[u] = timer
    children = 0
    
    for v in adj[u]:
        if disc[v] == 0:
            children++
            dfs(v, u)
            low[u] = min(low[u], low[v])
            
            // non-root 판정
            if parent != -1 and low[v] >= disc[u]:
                is_articulation[u] = true
        else if v != parent:
            // back edge
            low[u] = min(low[u], disc[v])
    
    // root 판정
    if parent == -1 and children >= 2:
        is_articulation[u] = true

for each component root r:
    dfs(r, -1)

구현

// 단절점 탐지, O(V+E)
#include <bits/stdc++.h>
using namespace std;

int V, E, timer = 0;
vector<int> adj[100005];
int disc[100005], low[100005];
bool is_cut[100005];

void dfs(int u, int p) {
  disc[u] = low[u] = ++timer;
  int children = 0;
  for (int v : adj[u]) {
      if (!disc[v]) {
          children++;
          dfs(v, u);
          low[u] = min(low[u], low[v]);
          if (p != -1 && low[v] >= disc[u])
              is_cut[u] = true;
      } else if (v != p) {
          low[u] = min(low[u], disc[v]);
      }
  }
  if (p == -1 && children >= 2)
      is_cut[u] = true;
}

int main() {
  cin >> V >> E;
  for (int i = 0; i < E; i++) {
      int u, v; cin >> u >> v;
      adj[u].push_back(v);
      adj[v].push_back(u);
  }
  for (int i = 1; i <= V; i++) {
      if (!disc[i]) dfs(i, -1);
  }
  vector<int> cuts;
  for (int i = 1; i <= V; i++)
      if (is_cut[i]) cuts.push_back(i);
  cout << cuts.size() << "\n";
  for (int x : cuts) cout << x << " ";
}

# 단절점 탐지, O(V+E)
import sys
sys.setrecursionlimit(200005)
input = sys.stdin.readline

V, E = map(int, input().split())
adj = [[] for _ in range(V + 1)]
for _ in range(E):
  u, v = map(int, input().split())
  adj[u].append(v)
  adj[v].append(u)

disc = [0] * (V + 1)
low = [0] * (V + 1)
is_cut = [False] * (V + 1)
timer = 0

def dfs(u, p):
  global timer
  timer += 1
  disc[u] = low[u] = timer
  children = 0
  for v in adj[u]:
      if disc[v] == 0:
          children += 1
          dfs(v, u)
          low[u] = min(low[u], low[v])
          if p != -1 and low[v] >= disc[u]:
              is_cut[u] = True
      elif v != p:
          low[u] = min(low[u], disc[v])
  if p == -1 and children >= 2:
      is_cut[u] = True

for i in range(1, V + 1):
  if disc[i] == 0:
      dfs(i, -1)

cuts = [i for i in range(1, V + 1) if is_cut[i]]
print(len(cuts))
print(*cuts)

// 단절점 탐지, O(V+E)
import java.util.*;
import java.io.*;
public class Main {
  static int V, E, timer = 0;
  static ArrayList<Integer>[] adj;
  static int[] disc, low;
  static boolean[] isCut;
  
  static void dfs(int u, int p) {
      disc[u] = low[u] = ++timer;
      int children = 0;
      for (int v : adj[u]) {
          if (disc[v] == 0) {
              children++;
              dfs(v, u);
              low[u] = Math.min(low[u], low[v]);
              if (p != -1 && low[v] >= disc[u])
                  isCut[u] = true;
          } else if (v != p) {
              low[u] = Math.min(low[u], disc[v]);
          }
      }
      if (p == -1 && children >= 2)
          isCut[u] = true;
  }
  
  public static void main(String[] args) throws IOException {
      BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
      StringTokenizer st = new StringTokenizer(br.readLine());
      V = Integer.parseInt(st.nextToken());
      E = Integer.parseInt(st.nextToken());
      adj = new ArrayList[V + 1];
      for (int i = 1; i <= V; i++) adj[i] = new ArrayList<>();
      disc = new int[V + 1];
      low = new int[V + 1];
      isCut = new boolean[V + 1];
      for (int i = 0; i < E; i++) {
          st = new StringTokenizer(br.readLine());
          int u = Integer.parseInt(st.nextToken());
          int v = Integer.parseInt(st.nextToken());
          adj[u].add(v);
          adj[v].add(u);
      }
      for (int i = 1; i <= V; i++) {
          if (disc[i] == 0) dfs(i, -1);
      }
      List<Integer> cuts = new ArrayList<>();
      for (int i = 1; i <= V; i++)
          if (isCut[i]) cuts.add(i);
      System.out.println(cuts.size());
      for (int x : cuts) System.out.print(x + " ");
  }
}

stdin

결과

2
3 4

복잡도

항목	값
시간	O(V + E)
공간	O(V) (disc, low, recursion stack)
전처리	DFS 한 번

변형

단절선 (Bridge)

간선 (u, v) 가 단절선 (bridge, cut edge) ⇔ DFS 트리 상에서 tree edge 이고 low[v] > disc[u].

단절점과 거의 동일 로직, 부등호만 > (등호 제외).

if (low[v] > disc[u]) {
    // (u, v) is a bridge
}

이중 연결 컴포넌트 (Biconnected Component)

단절점을 제거해도 연결된 채로 남는 최대 부분 그래프. DFS 중 스택에 간선을 쌓다가 단절점 발견 시 pop 하여 하나의 BCC 를 구성.

3-edge-connectivity / 3-vertex-connectivity

단절점 2개 이상 제거해야 분리되는 그래프. 선형 시간 알고리즘은 복잡하며, 흔히 network flow 로 접근.

함정

1. root 판정 누락

root 는 자식 2개 이상일 때만 단절점. non-root 판정 로직과 다르다.

if (parent == -1 && children >= 2)
    is_cut[u] = true;

2. 부모 간선을 back edge 로 착각

무향 그래프에서 (u, v) 와 (v, u) 가 모두 인접 리스트에 있다. v == parent 인 경우 back edge 로 처리하면 안 됨.

else if (v != parent) {
    low[u] = min(low[u], disc[v]);
}

3. 다중 컴포넌트 처리 안 함

그래프가 애초에 분리되어 있으면 각 컴포넌트마다 dfs 호출 필요.

for (int i = 1; i <= V; i++)
    if (!disc[i]) dfs(i, -1);

4. disc 와 low 의 의미 혼동

disc[u]: u 를 처음 방문한 시각 (변하지 않음).
low[u]: u 서브트리에서 back edge 로 도달 가능한 가장 빠른 시각 (갱신됨).

응용

문제 유형	설명
네트워크 취약점	단절점 = 장애 시 네트워크 분리
도로망 / 전력망	도로 하나로만 연결된 섬, 전력 허브
이중 연결 그래프	단절점 없는 그래프, 어떤 정점도 제거 가능
단절선 (Bridge)	간선 버전, 제거 시 분리되는 간선

BOJ 연습 문제

번호	제목	정답률	링크
BOJ 11266	단절점	-	kokoa-lab
BOJ 11400	단절선	-	kokoa-lab
BOJ 14675	단절점과 단절선	-	kokoa-lab

참고

이 글의 용어 (3개)

강한 연결 요소 (SCC)algorithm: 정의 강한 연결 요소 (Strongly Connected Component, SCC) 는 방향 그래프에서 서로 도달 가능한 정점들의 최대 부분 집합. SCC 내 임의 두 정점 u…
깊이 우선 탐색 (DFS)algorithm: 정의 깊이 우선 탐색 (Depth-First Search, DFS) 는 그래프 G=(V, E) 에서 갈 수 있는 만큼 깊이 들어가다가 막히면 백트래킹하는 알고리즘. 스택 (LIF…
이중 연결 요소 (BCC, Biconnected Component)algorithm: 정의 이중 연결 요소 (Biconnected Component, BCC) 는 무방향 그래프에서 정점 하나를 제거해도 연결성이 유지되는 최대 부분 그래프. 단절점 (articula…