연결성 문제와 Tarjan 알고리즘의 역할
그래프 이론에서 우리는 다양한 연결성 문제를 다루게 된다. 방향 그래프에서는 강결합 성분(SCC)을 찾는 문제가 있으며, 무방향 그래프에서는 절단선(bridge), 절단점(cut vertex), 그리고 이들을 기반으로 한 이중 연결 성분(biconnected components) 분석이 중요하다. 이러한 문제들에 대해 Tarjan 알고리즘은 깊이 우선 탐색(DFS)을 기반으로 효율적인 해법을 제공한다.
강결합 성분(SCC) 탐색
방향 그래프에서 두 정점 간에 서로 도달 가능한 관계를 강결합이라 하고, 이를 만족하는 최대 부분그래프를 강결합 성분(SCC)이라 한다. SCC는 전이성을 가지며, 전체 그래프를 여러 개의 SCC로 분할하면 결과적으로 사이클이 없는 DAG(Directed Acyclic Graph)를 얻을 수 있다.
Tarjan의 SCC 알고리즘은 DFS를 수행하면서 각 정점에 대해 두 가지 값을 기록한다:
dfn[u]: 정점 u가 방문된 순서 (DFS 번호)low[u]: u에서 출발해 트리 간선과 역방향 간선을 통해 도달 가능한 정점 중 가장 작은 dfn 값
특정 정점
u에서
dfn[u] == low[u]일 경우, 이는
u가 하나의 SCC의 루트임을 의미하며, 스택에서
u까지의 모든 정점들이 동일한 SCC에 속하게 된다.
int dfn[MAXN], low[MAXN], stk[MAXN], top = 0, sccId[MAXN], sccCnt = 0;
bool inStack[MAXN];
int timer = 0;
void findSCC(int u, vector<vector<int>>& graph) {
dfn[u] = low[u] = ++timer;
stk[++top] = u;
inStack[u] = true;
for (int v : graph[u]) {
if (!dfn[v]) {
findSCC(v, graph);
low[u] = min(low[u], low[v]);
} else if (inStack[v]) {
low[u] = min(low[u], dfn[v]);
}
}
if (dfn[u] == low[u]) {
++sccCnt;
while (true) {
int node = stk[top--];
inStack[node] = false;
sccId[node] = sccCnt;
if (node == u) break;
}
}
}
이 과정 후, 각 SCC를 하나의 정점으로 압축하면 DAG가 되므로, 위상 정렬이나 DP 등을 적용할 수 있다. 또한 2-SAT 문제의 해 존재 여부 판별에도 사용된다.
절단선과 이중 간선 연결 성분
무방향 그래프에서 절단선(bridge)은 제거 시 연결 요소의 개수가 증가하는 간선이다. 이를 찾기 위해 Tarjan 알고리즘은 DFS 트리를 구성하고, 자식 정점
v에 대해
low[v] > dfn[u]일 때 간선
(u, v)가 절단선임을 판단한다. 이는
v가 부모
u보다 더 위쪽 정점으로 돌아갈 경로가 없음을 의미한다.
각 절단선을 제외한 나머지 간선만을 이용하여 도달 가능한 정점 집합이 하나의 이중 간선 연결 성분(edge-biconnected component)이 된다.
vector<bool> isBridge;
vector<int> edgeDfn, edgeLow;
int edgeTimer = 0;
void findBridges(int u, int parentEdge, int parentId,
const vector<vector<pair<int, int>>>& adj) {
edgeDfn[parentId] = edgeLow[parentId] = ++edgeTimer;
for (auto [v, eid] : adj[u]) {
if (eid == parentEdge) continue;
if (!edgeDfn[eid]) {
findBridges(v, eid ^ 1, eid, adj);
edgeLow[eid] = min(edgeLow[eid], edgeLow[v]);
if (edgeLow[v] > edgeDfn[u]) {
isBridge[eid] = isBridge[eid ^ 1] = true;
}
} else {
edgeLow[eid] = min(edgeLow[eid], edgeDfn[v]);
}
}
}
절단점과 이중 점 연결 성분
절단점(cut vertex)은 삭제 시 연결 성분의 수가 증가하는 정점이다. 절단점을 포함할 수 있는 여러 개의 이중 점 연결 성분(point-biconnected component)이 존재하며, 이들은 오직 절단점 하나만을 공유할 수 있다.
DFS 도중 정점
u의 자식
v에 대해
low[v] ≥ dfn[u]이면,
u는 절단점이며
v를 루트로 하는 서브트리의 정점들과 함께 하나의 이중 점 연결 성분을 형성한다. 단, 루트 정점은 자식이 두 개 이상일 때만 절단점이 된다.
이중 점 연결 성분을 추출하기 위해 스택에 간선이나 정점을 저장하며, 조건 만족 시 스택에서 해당 성분을 추출한다.
vector<int> pointDfn, pointLow;
stack<int> nodeStack;
vector<vector<int>> biconnectedComps;
int compCounter = 0;
void findPointBiconnected(int u, int parent,
const vector<vector<int>>& adj) {
pointDfn[u] = pointLow[u] = ++timer;
nodeStack.push(u);
int children = 0;
for (int v : adj[u]) {
if (v == parent) continue;
if (!pointDfn[v]) {
++children;
findPointBiconnected(v, u, adj);
pointLow[u] = min(pointLow[u], pointLow[v]);
if ((parent != -1 && pointLow[v] >= pointDfn[u]) ||
(parent == -1 && children > 1)) {
vector<int> comp;
while (true) {
int w = nodeStack.top(); nodeStack.pop();
comp.push_back(w);
if (w == v) break;
}
comp.push_back(u); // u는 스택에 남김
biconnectedComps.push_back(comp);
}
} else {
pointLow[u] = min(pointLow[u], pointDfn[v]);
}
}
}
원-사각 트리(Circle-Square Tree)의 활용
각 이중 점 연결 성분마다 새로운 "사각 정점(square node)"을 생성하고, 해당 성분에 속한 모든 원래 정점(원 정점)을 사각 정점과 연결하면 원-사각 트리가 만들어진다. 이 구조는 원래 그래프의 복잡한 사이클 구조를 트리 형태로 변환하여 경로 쿼리, 필수 통과 정점 분석 등에 유리하다.
예를 들어, 두 정점 사이의 가능한 경로는 원-사각 트리 상의 경로와 그 경로에 인접한 사각 정점에 연결된 원 정점들을 포함하게 된다. 또한 LCA가 사각 정점인지 여부에 따라 경로 해석 방식이 달라질 수 있어 주의가 필요하다. 이러한 구조는 선인장 그래프(cactus graph)에서의 최단 거리 계산 등 고난도 문제 해결에 핵심적인 역할을 한다.