브리지와 단절점

정의. 연결된 무향 그래프에서 제거하면 그래프가 비연결 그래프가 되는 간선을 다리라고 합니다.

정의. 연결된 무향 그래프에서 제거하면 그래프가 비연결 그래프가 되는 정점을 단절점이라고 합니다.

이를 찾는 것이 흥미로운 문제의 예는 다음과 같습니다. 네트워크 토폴로지(컴퓨터와 그 사이의 물리적 연결)가 주어지고, 모든 단일 장애 지점, 즉 그것이 없으면 서로 간에 경로가 존재하지 않는 두 노드가 생기게 되는 노드와 연결을 찾아야 합니다.

각 간선 $(u, v)$를 하나씩 제거하고 경로 $u \leadsto v$가 존재하는지 확인하는 단순한 알고리즘은 $O(m^2)$의 연산이 필요합니다. 브리지를 더 빠르게 찾는 방법을 익히기 위해, 먼저 깊이 우선 탐색과 관련된 몇 가지 명제를 세워 봅시다.

임의의 정점에서 DFS를 실행합시다. 새로운 종류의 간선을 정의합시다:

• 순방향 간선은 dfs에서 이동이 일어난 간선입니다.

• 역방향 간선은 dfs에서 이동이 일어나지 않은 간선입니다.

어떤 역방향 간선 $(u, v)$도 브리지가 될 수 없다는 점에 주목하십시오. 이 간선을 제거하더라도 정방향 간선으로 이루어진 부분 그래프가 연결된 트리이므로 $u$에서 $v$로 가는 경로가 여전히 존재하기 때문입니다.

따라서 남은 일은 모든 트리 간선을 확인하는 것뿐입니다. 이것만으로도 조금 나아졌습니다. 이러한 알고리즘은 $O(n m)$에 동작합니다.

이를 선형 시간(dfs 한 번의 순회)으로 최적화하는 데에는 다음 관찰이 도움이 됩니다. 역방향 간선은 오직 “위쪽”, 즉 그래프 탐색 트리에서 어떤 조상으로만 향할 수 있고 다른 “가지"로는 향할 수 없습니다. 그렇지 않다면 dfs가 이 간선을 더 일찍 발견했을 것이고, 그 간선은 역방향 간선이 아니라 순방향 간선이 되었을 것입니다.

그러면 트리 간선 $v \to u$가 다리인지 판별하기 위해 다음 기준을 사용할 수 있습니다. 정점 $v$의 깊이 $h_v$가 $u$의 서브트리에 속한 어떤 정점과 역방향 간선으로 연결된 모든 정점의 깊이의 최솟값보다 작습니다.

명확성을 위해 이 값을 $d_u$로 표기하겠습니다. 이 값은 탐색 중에 다음 공식으로 계산할 수 있습니다.

이 조건($h_v < d_u$)이 성립하지 않으면 간선 $(v, u)$를 사용하지 않고 $u$에서 $v$의 어떤 조상 또는 $v$ 자신으로 가는 경로가 존재하며, 그렇지 않은 경우에는 그 반대입니다.

const int maxn = 1e5;

bool used[maxn];
int h[maxn], d[maxn];

void dfs(int v, int p = -1) {
    used[v] = true;
    d[v] = h[v] = (p == -1 ? 0 : h[p] + 1);
    for (int u : g[v]) {
        if (u != p) {
            if (used[u]) // если ребро обратное
                d[v] = min(d[v], h[u]);
            else { // если ребро прямое
                dfs(u, v);
                d[v] = min(d[v], d[u]);
                if (h[v] < d[u]) {
                    // если нельзя другим путем добраться в v или выше,
                    // то ребро (v, u) -- мост
                }
            }
        }
    }
}

참고. 정점의 깊이 대신 $tin$을 사용하는 알고리즘이 더 널리 알려져 있지만, 저자는 그 알고리즘이 이해하기에 조금 더 어렵다고 생각합니다.

#단절점

단절점을 찾는 문제는 다리를 찾는 문제와 크게 다르지 않습니다.

정점 $v$는 그 자식 중 어떤 $u$에서 간선 $(v, u)$를 사용하지 않고는 $v$의 조상으로 갈 수 없을 때 단절점입니다. 특정 트리 간선 $v \to u$에 대해서는 이 사실을 다음과 같이 확인할 수 있습니다: $h_v \leq d_u$ (이번에는 부등식이 등호를 포함하는데, 어떤 정점에서 자기 자신까지만 도달할 수 있더라도 그 정점은 여전히 단절점이 되기 때문입니다).

이 사실을 이용하면 알고리즘을 거의 그대로 둘 수 있습니다. 모든 정방향 간선 $v \to u$에 대해 이 기준을 확인하면 됩니다:

void dfs(int v, int p = -1) {
    used[v] = 1;
    d[v] = h[v] = (p == -1 ? 0 : h[p] + 1);
    int children = 0;
    for (int u : g[v]) {
        if (u != p) {
            if (used[u])
                d[v] = min(d[v], h[u]);
            else {
                dfs(u, v);
                d[v] = min(d[v], d[u]);
                if (h[v] <= d[u] && p != -1) { // корень (p == -1) обрабатываем отдельно
                    // v -- точка сочленения
                    // (это условие может выполниться много раз для разных детей)
                }
              	children++;
            }
        }
    }
    if (p == -1 && children > 1) {
        // v -- корень и точка сочленения
    }
}

유일한 예외 상황은 루트입니다. 정의상 루트에는 다른 어떤 정점보다 먼저 들어가기 때문입니다. 하지만 이 경우의 해결책은 매우 간단합니다. 탐색에서 루트가 둘 이상의 가지를 가졌는지 확인하기만 하면 됩니다(루트를 제거하면 루트의 서브트리들은 서로 연결되지 않게 됩니다).