최소 공통 조상 - Tarjan의 오프라인 알고리즘¶

$n$개의 노드로 이루어진 트리 $G$가 있고, $(u, v)$ 형태의 쿼리가 $m$개 있습니다. 각 쿼리 $(u, v)$마다 정점 $u$와 $v$의 최소 공통 조상, 즉 $u$와 $v$ 모두의 조상이면서 트리에서 깊이가 가장 깊은 노드를 찾으려고 합니다. 노드 $v$는 $v$ 자신의 조상이기도 하므로, LCA가 두 노드 중 하나일 수도 있습니다.

이 글에서는 문제를 오프라인으로 해결합니다. 즉, 모든 쿼리를 미리 알고 있다고 가정하므로 원하는 순서대로 쿼리에 답할 수 있습니다. 다음 알고리즘을 사용하면 $m$개의 쿼리 전체에 총 $O(n + m)$ 시간에 답할 수 있습니다. 즉, $m$이 충분히 크면 쿼리 하나당 $O(1)$입니다.

알고리즘¶

이 알고리즘은 1979년에 이를 발견한 Robert Tarjan의 이름을 딴 것입니다. Tarjan은 이 알고리즘에서 많이 사용하는 서로소 집합 유니온 자료 구조에도 여러 기여를 했습니다.

이 알고리즘은 트리를 DFS로 한 번 순회하여 모든 쿼리에 답합니다. 구체적으로, 쿼리 $(u, v)$는 노드 $v$를 이미 방문했다면 노드 $u$에서 답하고, 그 반대의 경우도 마찬가지입니다.

이제 현재 노드 $v$에 있고, 재귀적인 DFS 호출을 이미 마쳤으며, 쿼리 $(u, v)$의 다른 노드 $u$도 이미 방문했다고 가정합시다. 이 두 노드의 LCA를 찾는 방법을 알아봅시다.

$\text{LCA}(u, v)$는 노드 $v$이거나 $v$의 조상 중 하나라는 점에 유의하십시오. 따라서 $v$의 조상($v$ 포함) 중에서 노드 $u$를 자손으로 갖는 가장 낮은 노드를 찾아야 합니다. 또한 $v$를 고정하면 트리에서 방문한 노드들이 서로소인 집합 여러 개로 나뉜다는 점에 유의하십시오. 노드 $v$의 각 조상 $p$는 자기만의 집합을 가지며, 이 집합에는 $p$ 자신과, $p$의 자식 중 $v$에서 트리의 루트로 가는 경로에 속하지 않는 자식을 루트로 하는 모든 서브트리가 들어 있습니다. 노드 $u$를 포함하는 집합이 $\text{LCA}(u, v)$를 결정합니다. LCA는 그 집합의 대표, 즉 $v$와 트리의 루트 사이의 경로 위에 있는 노드입니다.

이제 이 집합들을 모두 효율적으로 관리하는 방법만 알면 됩니다. 이를 위해 DSU 자료 구조를 사용합니다. 랭크에 의한 합치기(Union by rank)를 적용할 수 있도록, 각 집합의 실제 대표($v$와 트리의 루트 사이의 경로 위에 있는 값)를 배열 ancestor에 저장합니다.

DFS의 구현을 살펴봅시다. 현재 노드 $v$를 방문하고 있다고 가정합시다. 이 노드를 DSU의 새 집합에 넣습니다: ancestor[v] = v. 평소처럼 $v$의 모든 자식을 처리합니다. 이를 위해 먼저 해당 자식 노드에서 DFS를 재귀적으로 호출한 다음, 그 노드와 그 서브트리 전체를 $v$의 집합에 추가해야 합니다. 이는 함수 union_sets와 그 뒤에 오는 대입 ancestor[find_set(v)] = v로 할 수 있습니다(union_sets가 집합의 대표를 바꿀 수 있으므로 이 대입이 필요합니다).

마지막으로 모든 자식을 처리한 뒤에는 $u$를 이미 방문한 $(u, v)$ 형태의 모든 쿼리에 답할 수 있습니다. 쿼리의 답, 즉 $u$와 $v$의 LCA는 노드 ancestor[find_set(u)]입니다. 각 쿼리에 한 번만 답한다는 것은 쉽게 알 수 있습니다.

이 알고리즘의 시간 복잡도를 구해 봅시다. 첫째로, DFS 때문에 $O(n)$이 소요됩니다. 둘째로, union_sets 함수 호출이 $n$번 일어나므로 이 역시 $O(n)$이 됩니다. 셋째로, 각 쿼리마다 find_set을 호출하므로 $O(m)$이 됩니다. 따라서 전체 시간 복잡도는 $O(n + m)$이며, 이는 $m$이 충분히 클 때 쿼리 하나에 답하는 데 $O(1)$이 걸리는 것과 같다는 뜻입니다.

구현¶

다음은 이 알고리즘의 구현입니다. DSU는 아무런 수정 없이 그대로 사용할 수 있으므로 DSU의 구현은 포함하지 않았습니다.

vector<vector<int>> adj;
vector<vector<int>> queries;
vector<int> ancestor;
vector<bool> visited;

void dfs(int v)
{
    visited[v] = true;
    ancestor[v] = v;
    for (int u : adj[v]) {
        if (!visited[u]) {
            dfs(u);
            union_sets(v, u);
            ancestor[find_set(v)] = v;
        }
    }
    for (int other_node : queries[v]) {
        if (visited[other_node])
            cout << "LCA of " << v << " and " << other_node
                 << " is " << ancestor[find_set(other_node)] << ".\n";
    }
}

void compute_LCAs() {
    // initialize n, adj and DSU
    // for (each query (u, v)) {
    //    queries[u].push_back(v);
    //    queries[v].push_back(u);
    // }

    ancestor.resize(n);
    visited.assign(n, false);
    dfs(0);
}