온라인으로 브리지 찾기¶

무방향 그래프가 주어집니다. 브리지란 제거하면 그래프가 비연결 상태가 되는(더 정확히 말하면 연결 요소의 개수가 증가하는) 간선입니다. 우리의 과제는 주어진 그래프의 모든 브리지를 찾는 것입니다.

이 과제를 비형식적으로 표현하면 다음과 같습니다: 주어진 도로 지도에서 "중요한" 도로, 즉 그중 어느 하나라도 제거하면 일부 도시에서 다른 도시로 도달할 수 없게 되는 도로를 모두 찾아야 합니다.

이 과제를 깊이 우선 탐색 순회로 해결하는 $O(N+M)$에 브리지 찾기 글이 이미 있습니다. 이 알고리즘은 훨씬 더 복잡하지만 한 가지 큰 장점이 있습니다: 이 글에서 설명하는 알고리즘은 온라인으로 동작하며, 이는 입력 그래프를 미리 알 필요가 없다는 뜻입니다. 간선은 한 번에 하나씩 추가되며, 각 추가 후에 알고리즘은 현재 그래프의 모든 브리지를 다시 계산합니다. 다시 말해, 이 알고리즘은 동적으로 변하는 그래프에서 효율적으로 동작하도록 설계되었습니다.

문제를 더 엄밀하게 서술하면 다음과 같습니다: 처음에 그래프는 비어 있으며 $n$개의 정점으로 이루어져 있습니다. 그다음 그래프에 추가되는 간선을 나타내는 정점 쌍 $(a, b)$를 입력받습니다. 간선을 하나 입력받을 때마다, 즉 각 간선을 추가한 후에 그래프의 현재 브리지 개수를 출력하십시오.

모든 브리지의 목록을 유지하는 것과 2-간선-연결 요소를 명시적으로 관리하는 것도 가능합니다.

아래에서 설명하는 알고리즘은 $O(n \log n + m)$ 시간에 동작하며, 여기서 $m$은 간선의 개수입니다. 이 알고리즘은 서로소 집합 유니온 자료 구조를 기반으로 합니다. 하지만 이 글의 구현은 랭크에 의한 합치기(Union by Rank)가 없는 단순화된 버전의 DSU를 사용하므로 $O(n \log n + m \log n)$ 시간이 걸립니다.

알고리즘¶

먼저 $k$-간선-연결 요소를 정의합시다: 이는 $k$개 미만의 간선을 제거하면 언제나 연결 상태를 유지하는 연결 요소입니다.

브리지가 그래프를 2-간선-연결 요소들로 분할한다는 것은 매우 쉽게 알 수 있습니다. 2-간선-연결 요소 각각을 하나의 정점으로 압축하고 압축된 그래프에 브리지만 간선으로 남기면 비순환 그래프, 즉 포레스트를 얻습니다.

아래에서 설명하는 알고리즘은 2-간선-연결 요소뿐만 아니라 이 포레스트도 명시적으로 유지합니다.

처음에 그래프가 비어 있을 때에는 그래프가 서로 연결되지 않은 $n$개의 2-간선-연결 요소를 포함한다는 것이 자명합니다.

다음 간선 $(a, b)$를 추가할 때에는 세 가지 상황이 발생할 수 있습니다:

두 정점 $a$와 $b$가 같은 2-간선-연결 요소에 속하는 경우 - 이때 이 간선은 브리지가 아니며 포레스트 구조를 전혀 바꾸지 않으므로, 이 간선은 그냥 건너뛸 수 있습니다.

따라서 이 경우 브리지의 개수는 변하지 않습니다.
정점 $a$와 $b$가 완전히 다른 연결 요소에 속하는 경우, 즉 각각 서로 다른 트리의 일부인 경우입니다. 이 경우 간선 $(a, b)$는 새로운 브리지가 되고, 두 트리는 하나로 합쳐집니다(기존의 브리지는 모두 그대로 남습니다).

따라서 이 경우 브리지의 개수는 1 증가합니다.
정점 $a$와 $b$가 하나의 연결 요소에 속하지만 서로 다른 2-간선-연결 요소에 속하는 경우입니다. 이 경우 이 간선은 기존 브리지 일부와 함께 사이클을 이룹니다. 이 브리지들은 모두 더 이상 브리지가 아니게 되며, 그 결과 생긴 사이클은 새로운 2-간선-연결 요소로 압축해야 합니다.

따라서 이 경우 브리지의 개수는 1 이상 감소합니다.

따라서 전체 작업은 2-간선-연결 요소들의 포레스트 위에서 이 모든 연산을 효율적으로 구현하는 문제로 귀결됩니다.

포레스트를 저장하기 위한 자료 구조¶

필요한 자료 구조는 서로소 집합 유니온 하나뿐입니다. 사실 이 구조의 사본을 두 개 만듭니다. 하나는 연결 요소를 관리하는 데 쓰고, 다른 하나는 2-간선-연결 요소를 관리하는 데 씁니다. 그리고 이에 더하여 2-간선-연결 요소들의 포레스트에 있는 트리의 구조를 포인터로 저장합니다. 각 2-간선-연결 요소는 트리에서 자신의 조상의 인덱스 par[]를 저장합니다.

이제 구현하는 방법을 익혀야 하는 모든 연산을 차례대로 살펴보겠습니다.

두 정점이 같은 연결 / 2-간선-연결 요소에 속하는지 확인합니다. 이는 일반적인 DSU 알고리즘으로 수행되며, DSU의 대표 원소를 찾아서 비교하기만 하면 됩니다.
어떤 간선 $(a, b)$에 대해 두 트리를 합칩니다. 정점 $a$와 정점 $b$ 모두 각자 트리의 루트가 아닐 수 있으므로, 이 두 트리를 연결하는 유일한 방법은 둘 중 하나의 루트를 바꾸는 것입니다. 예를 들어 정점 $a$가 속한 트리의 루트를 $a$로 바꾼 다음, $a$의 조상을 $b$로 설정하여 다른 트리에 붙일 수 있습니다.

그러나 루트 변경 연산의 효율성에 대한 의문이 생깁니다. 루트가 $r$인 트리의 루트를 정점 $v$로 바꾸려면, $v$와 $r$ 사이의 경로 위에 있는 모든 정점을 방문하여 포인터 par[]를 반대 방향으로 바꾸고, 연결 요소를 담당하는 DSU에서 조상에 대한 참조도 변경해야 합니다.

따라서 루트 변경의 비용은 $O(h)$이며, 여기서 $h$는 트리의 높이입니다. 비용이 $O(\text{size})$라고 더 느슨하게 추정할 수도 있으며, 여기서 $\text{size}$는 트리에 있는 정점의 수입니다. 최종 복잡도는 달라지지 않습니다.

이제 표준적인 기법을 적용합니다. 정점이 더 적은 트리의 루트를 바꿉니다. 그러면 최악의 경우는 크기가 거의 같은 두 트리가 합쳐질 때라는 것이 직관적으로 분명하지만, 그 결과는 크기가 두 배인 트리가 됩니다. 따라서 이러한 상황은 여러 번 일어날 수 없습니다.

일반적으로 전체 비용은 다음과 같은 점화식의 형태로 쓸 수 있습니다.

$$ T(n) = \max_{k = 1 \ldots n-1} \left\{ T(k) + T(n - k) + O(\min(k, n - k))\right\} $$

$T(n)$은 루트 변경과 트리 합치기를 통해 정점이 $n$개인 트리를 얻는 데 필요한 연산의 수입니다. 크기가 $n$인 트리는 크기가 $k$와 $n - k$인 더 작은 두 트리를 합쳐서 만들 수 있습니다. 이 점화식의 해는 $T(n) = O (n \log n)$입니다.

따라서 항상 두 트리 중 더 작은 쪽의 루트를 바꾼다면, 모든 루트 변경 연산에 드는 총 시간은 $O(n \log n)$이 됩니다.

각 연결 요소의 크기를 관리해야 하지만, DSU 자료 구조를 사용하면 어렵지 않게 할 수 있습니다.
새 간선 $(a, b)$를 추가하여 생기는 사이클을 찾습니다. $a$와 $b$는 이미 트리에서 연결되어 있으므로, 정점 $a$와 $b$의 최소 공통 조상을 찾아야 합니다. 사이클은 $b$에서 LCA까지의 경로, LCA에서 $a$까지의 경로, 그리고 $a$에서 $b$로 가는 간선으로 구성됩니다.

사이클을 찾은 후에는 발견한 사이클의 모든 정점을 하나의 정점으로 압축합니다. 이는 이미 사이클 길이에 비례하는 복잡도가 든다는 뜻이므로, 길이에 비례하는 어떤 LCA 알고리즘이든 사용할 수 있으며 빠른 알고리즘을 쓸 필요가 없습니다.

트리 구조에 대한 모든 정보는 조상 배열 par[]에 있으므로, 합리적인 LCA 알고리즘은 다음 하나뿐입니다. 정점 $a$와 $b$를 방문한 것으로 표시한 다음, 각각의 조상 par[a]와 par[b]로 이동하여 표시하고, 다시 그 조상으로 나아가는 과정을 이미 표시된 정점에 도달할 때까지 반복합니다. 이 정점이 우리가 찾는 LCA이며, $a$와 $b$에서 LCA까지의 경로를 다시 따라가면 사이클 위의 정점들을 찾을 수 있습니다.

이 알고리즘의 복잡도가 구하려는 사이클의 길이에 비례한다는 것은 자명합니다.
트리에 새 간선 $(a, b)$를 추가하여 생긴 사이클의 압축.

발견된 사이클의 모든 정점으로 이루어진 새로운 2-간선-연결 요소를 만들어야 합니다(발견된 사이클 자체가 여러 개의 2-간선-연결 요소로 이루어져 있을 수도 있지만, 이는 아무것도 바꾸지 않습니다). 또한 트리의 구조가 깨지지 않고 모든 포인터 par[]와 두 DSU가 여전히 올바르도록 이들을 압축해야 합니다.

이를 달성하는 가장 쉬운 방법은 사이클의 모든 정점을 그들의 LCA로 압축하는 것입니다. 실제로 LCA는 이 정점들 중 가장 높은 정점이므로, 그 조상 포인터 par[]는 바뀌지 않습니다. 루프의 나머지 정점들은 그냥 사라지므로 이 정점들의 조상은 갱신할 필요가 없습니다. 다만 2-간선-연결 요소의 DSU에서는 이 정점들이 모두 LCA를 가리키게 됩니다.

2-간선-연결 요소의 DSU는 랭크에 의한 합치기(Union by rank) 최적화 없이 구현할 것이므로, 쿼리당 평균 $O(\log n)$의 복잡도를 얻게 됩니다. 쿼리당 평균 $O(1)$의 복잡도를 달성하려면 사이클의 정점들을 랭크에 의한 합치기에 따라 합친 다음, 그에 맞게 par[]를 지정해야 합니다.

구현¶

다음은 전체 알고리즘의 최종 구현입니다.

앞서 언급했듯이, 단순함을 위해 2-간선-연결 요소의 DSU는 랭크에 의한 합치기 없이 작성되었으므로 결과 복잡도는 평균 $O(\log n)$이 됩니다.

또한 이 구현에서는 브리지 자체는 저장하지 않고 그 개수 bridges만 저장합니다. 하지만 모든 브리지의 set을 만드는 것은 어렵지 않습니다.

처음에 init() 함수를 호출합니다. 이 함수는 두 DSU를 초기화하고(각 정점마다 별도의 집합을 만들고 크기를 1로 설정합니다), 조상 par를 설정합니다.

주요 함수는 add_edge(a, b)이며, 새 간선을 처리하고 추가합니다.

vector<int> par, dsu_2ecc, dsu_cc, dsu_cc_size;
int bridges;
int lca_iteration;
vector<int> last_visit;

void init(int n) {
    par.resize(n);
    dsu_2ecc.resize(n);
    dsu_cc.resize(n);
    dsu_cc_size.resize(n);
    lca_iteration = 0;
    last_visit.assign(n, 0);
    for (int i=0; i<n; ++i) {
        dsu_2ecc[i] = i;
        dsu_cc[i] = i;
        dsu_cc_size[i] = 1;
        par[i] = -1;
    }
    bridges = 0;
}

int find_2ecc(int v) {
    if (v == -1)
        return -1;
    return dsu_2ecc[v] == v ? v : dsu_2ecc[v] = find_2ecc(dsu_2ecc[v]);
}

int find_cc(int v) {
    v = find_2ecc(v);
    return dsu_cc[v] == v ? v : dsu_cc[v] = find_cc(dsu_cc[v]);
}

void make_root(int v) {
    int root = v;
    int child = -1;
    while (v != -1) {
        int p = find_2ecc(par[v]);
        par[v] = child;
        dsu_cc[v] = root;
        child = v;
        v = p;
    }
    dsu_cc_size[root] = dsu_cc_size[child];
}

void merge_path (int a, int b) {
    ++lca_iteration;
    vector<int> path_a, path_b;
    int lca = -1;
    while (lca == -1) {
        if (a != -1) {
            a = find_2ecc(a);
            path_a.push_back(a);
            if (last_visit[a] == lca_iteration){
                lca = a;
                break;
                }
            last_visit[a] = lca_iteration;
            a = par[a];
        }
        if (b != -1) {
            b = find_2ecc(b);
            path_b.push_back(b);
            if (last_visit[b] == lca_iteration){
                lca = b;
                break;
                }
            last_visit[b] = lca_iteration;
            b = par[b];
        }

    }

    for (int v : path_a) {
        dsu_2ecc[v] = lca;
        if (v == lca)
            break;
        --bridges;
    }
    for (int v : path_b) {
        dsu_2ecc[v] = lca;
        if (v == lca)
            break;
        --bridges;
    }
}

void add_edge(int a, int b) {
    a = find_2ecc(a);
    b = find_2ecc(b);
    if (a == b)
        return;

    int ca = find_cc(a);
    int cb = find_cc(b);

    if (ca != cb) {
        ++bridges;
        if (dsu_cc_size[ca] > dsu_cc_size[cb]) {
            swap(a, b);
            swap(ca, cb);
        }
        make_root(a);
        par[a] = dsu_cc[a] = b;
        dsu_cc_size[cb] += dsu_cc_size[a];
    } else {
        merge_path(a, b);
    }
}

2-간선-연결 요소의 DSU는 벡터 dsu_2ecc에 저장되며, 대표를 반환하는 함수는 find_2ecc(v)입니다. 이 함수는 코드의 나머지 부분에서 여러 번 사용되는데, 여러 정점을 하나로 압축한 뒤에는 이 정점들이 모두 사라지고 대신 리더만이 2-간선-연결 요소의 포레스트에서 올바른 조상 par를 가지기 때문입니다.

연결 요소의 DSU는 벡터 dsu_cc에 저장되며, 요소의 크기를 저장하기 위한 추가 벡터 dsu_cc_size도 있습니다. 함수 find_cc(v)는 연결 요소의 리더(실제로는 트리의 루트)를 반환합니다.

트리의 루트 변경 make_root(v)는 위에서 설명한 대로 동작합니다: 정점 $v$에서 조상들을 거쳐 루트 정점까지 올라가면서, 매번 조상 par를 반대 방향으로 바꿉니다. 연결 요소의 대표에 대한 링크 dsu_cc도 새 루트 정점을 가리키도록 갱신됩니다. 루트 변경 후에는 새 루트에 연결 요소의 올바른 크기를 지정해야 합니다. 또한 이미 압축된 다른 정점이 아니라 2-간선-연결 요소의 대표를 얻기 위해 find_2ecc()를 호출하도록 주의해야 합니다.

사이클을 찾고 압축하는 함수 merge_path(a, b) 역시 위에서 설명한 대로 구현됩니다. 이 함수는 어떤 정점을 두 번째로 만날 때까지 두 노드를 동시에 올려 가며 $a$와 $b$의 LCA를 찾습니다. 효율성을 위해 LCA를 찾는 각 호출마다 고유한 식별자를 정하고, 지나간 정점들을 그 식별자로 표시합니다. 이 방식은 $O(1)$에 동작하며, $set$을 사용하는 것과 같은 다른 방법은 성능이 더 나쁩니다. 지나온 경로는 벡터 path_a와 path_b에 저장되며, 이를 이용해 LCA까지 경로를 한 번 더 따라가면서 사이클의 모든 정점을 얻습니다. 사이클의 모든 정점은 LCA에 붙이는 방식으로 압축되므로, 평균 복잡도는 $O(\log n)$입니다(랭크에 의한 합치기를 사용하지 않기 때문입니다). 지나온 간선은 모두 브리지였으므로, 사이클의 간선마다 1씩 뺍니다.

마지막으로 쿼리 함수 add_edge(a, b)는 정점 $a$와 $b$가 속한 연결 요소를 알아냅니다. 두 정점이 서로 다른 연결 요소에 속해 있다면, 더 작은 트리의 루트를 다시 정한 뒤 더 큰 트리에 붙입니다. 그렇지 않고 정점 $a$와 $b$가 같은 트리에 있지만 서로 다른 2-간선-연결 요소에 속해 있다면, 함수 merge_path(a, b)를 호출합니다. 이 함수는 사이클을 찾아내 하나의 2-간선-연결 요소로 압축합니다.