Хамгийн бага нийтлэг өвөг - Тарьяны офлайн алгоритм¶

Бидэнд $n$ зангилаатай мод $G$ ба $(u, v)$ хэлбэрийн $m$ асуулга байна. Асуулга $(u, v)$ бүрийн хувьд бид $u$ ба $v$ оройнуудын хамгийн бага нийтлэг өвгийг, өөрөөр хэлбэл $u$ ба $v$ хоёрын аль алины өвөг байх бөгөөд модонд хамгийн их гүнтэй зангилааг олохыг хүсэж байна. $v$ зангилаа нь мөн $v$-ийн өвөг тул LCA нь хоёр зангилааны нэг ч байж болно.

Энэ өгүүлэлд бид бодлогыг офлайнаар бодно, өөрөөр хэлбэл бид бүх асуулга урьдчилан мэдэгдэж байна гэж үзэх ба тиймээс асуулгад дуртай дарааллаараа хариулна. Дараах алгоритм бүх $m$ асуулгад нийт $O(n + m)$ хугацаанд, өөрөөр хэлбэл хангалттай том $m$-ийн хувьд асуулга бүрд $O(1)$-д хариулах боломж олгоно.

Алгоритм¶

Алгоритмыг 1979 онд түүнийг нээсэн, мөн энэ алгоритмд ихээхэн ашиглагдах Огтлолцолгүй олонлогийн нэгдэл өгөгдлийн бүтцэд бусад олон хувь нэмэр оруулсан Роберт Тарьяны нэрээр нэрлэсэн.

Алгоритм модны нэг DFS тойролтоор бүх асуулгад хариулна. Тухайлбал $(u, v)$ асуулгад $v$ зангилаад аль хэдийн зочилсон бол $u$ зангилаад хариулна, эсвэл эсрэгээр.

Тэгэхээр бид одоо $v$ зангилаад байгаа, рекурсив DFS дуудлагуудыг аль хэдийн хийсэн, мөн $(u, v)$ асуулгын хоёр дахь зангилаа $u$-д аль хэдийн зочилсон гэж үзье. Эдгээр хоёр зангилааны LCA-г хэрхэн олохыг сурцгаая.

$\text{LCA}(u, v)$ нь $v$ зангилаа эсвэл түүний өвгүүдийн нэг болохыг анхаарна уу. Тиймээс бид $v$-ийн өвгүүдийн (мөн $v$-г оруулаад) дундаас $u$ зангилаа удам нь байх хамгийн бага зангилааг олох хэрэгтэй. Мөн тогтмол $v$-ийн хувьд модны зочилсон зангилаанууд огтлолцолгүй олонлогуудын олонлог болон хуваагддагийг анхаарна уу. $v$ зангилааны өвөг $p$ бүр энэ зангилаа ба $v$-ээс модны үндэс хүртэлх замын хэсэг биш хүүхдүүдэд нь үндэстэй бүх дэд модыг агуулсан өөрийн олонлогтой байна. $u$ зангилааг агуулах олонлог нь $\text{LCA}(u, v)$-г тодорхойлно: LCA нь тэр олонлогийн төлөөлөгч, тухайлбал $v$ ба модны үндсийн хоорондох зам дээр орших зангилаа юм.

Бид зөвхөн эдгээр бүх олонлогийг үр ашигтай хөтөлж сурах хэрэгтэй. Энэ зорилгоор бид DSU өгөгдлийн бүтцийг хэрэглэнэ. Зэргээр нэгтгэхийг хэрэглэж чадахын тулд бид олонлог бүрийн жинхэнэ төлөөлөгчийг ($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)] зангилаа байх болно. Асуулгад зөвхөн нэг удаа хариулагдахыг харахад амархан.

Энэ алгоритмын time complexity-г тодорхойлъё. Нэгдүгээрт DFS-ээс болж бидэнд $O(n)$ байна. Хоёрдугаарт бидэнд $n$ удаа тохиолддог union_sets функцийн дуудлагууд байгаа нь мөн $O(n)$ өгнө. Гуравдугаарт бидэнд асуулга бүрийн хувьд find_set-ийн дуудлагууд байгаа нь $O(m)$ өгнө. Тиймээс нийт time complexity нь $O(n + m)$ бөгөөд энэ нь хангалттай том $m$-ийн хувьд нэг асуулгад хариулахад $O(1)$-тэй харгалзана гэсэн үг.

Implementation¶

Here is an implementation of this algorithm. The implementation of DSU has been not included, as it can be used without any modifications.

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);
}