Агуулгыг алгасах

Хүчтэй холбоост компонент ба конденсацийн граф

Тодорхойлолтууд

$G=(V,E)$ нь орой $V$, ирмэг $E \subseteq V \times V$-тэй чиглэлтэй граф байг. Бид $G$ дэх оройн тоог $n=|V|$, ирмэгийн тоог $m=|E|$ гэж тэмдэглэнэ. Энэ өгүүлэл дэх бүх тодорхойлолтыг мультиграф руу өргөтгөхөд амархан боловч бид түүнд анхаарлаа хандуулахгүй.

Дараах нөхцөлүүд биелж байвал оройнуудын дэд олонлог $C \subseteq V$-г хүчтэй холбоост компонент гэж нэрлэнэ:

  • бүх $u,v\in C$-ийн хувьд хэрэв $u \neq v$ бол $u$-ээс $v$ хүрэх зам ба $v$-ээс $u$ хүрэх зам оршин байна, мөн
  • дээрх нөхцөлийг зөрчихгүйгээр ямар ч орой нэмж болохгүй гэсэн утгаараа $C$ нь максимал байна.

Бид $G$-ийн хүчтэй холбоост компонентуудын олонлогийг $\text{SCC}(G)$ гэж тэмдэглэнэ. Эдгээр хүчтэй холбоост компонентууд хоорондоо огтлолцохгүй бөгөөд граф дахь бүх оройг бүрхэнэ. Ингэснээр олонлог $\text{SCC}(G)$ нь $V$-ийн хуваалт юм.

Хүчтэй холбоост компонентуудыг тодруулсан энэ граф $G_\text{example}$-г авч үзье:

drawing

Энд бидэнд $\text{SCC}(G_\text{example})=\{\{0,7\},\{1,2,3,5,6\},\{4,9\},\{8\}\}$ байна. Хүчтэй холбоост компонент бүрийн дотор бүх орой бие биендээ хүрч болохыг бид баталгаажуулж чадна.

Бид конденсацийн граф $G^{\text{SCC}}=(V^{\text{SCC}}, E^{\text{SCC}})$-г дараах байдлаар тодорхойлно:

  • $G^{\text{SCC}}$-ийн орой нь $G$-ийн хүчтэй холбоост компонентууд, өөрөөр хэлбэл $V^{\text{SCC}} = \text{SCC}(G)$, мөн
  • конденсацийн графын бүх орой $C_i,C_j$-ийн хувьд $C_i \neq C_j$ байх ба $G$-д $a$-ээс $b$ хүрэх ирмэг байхаар $a\in C_i$ ба $b\in C_j$ оршин байвал зөвхөн тэр үед л $C_i$-ээс $C_j$ хүрэх ирмэг байна.

$G_\text{example}$-ийн конденсацийн граф дараах байдалтай:

drawing

Конденсацийн графын хамгийн чухал шинж чанар нь түүний циклгүй байдал юм. Үнэндээ конденсацийн графт тодорхойлолтоороо 'гогцоо' байхгүй бөгөөд хэрэв конденсацийн графт хоёр буюу түүнээс олон оройгоор (хүчтэй холбоост компонентоор) дайран өнгөрөх цикл байсан бол хүрэх боломжийн улмаас эдгээр хүчтэй холбоост компонентуудын нэгдэл өөрөө нэг хүчтэй холбоост компонент байх ёстой болно: зөрчил.

Дараагийн хэсэгт тайлбарласан алгоритм өгөгдсөн граф дахь бүх хүчтэй холбоост компонентыг олно. Үүний дараа конденсацийн графыг байгуулж болно.

Косаражугийн алгоритм

Алгоритмын тайлбар

Тайлбарласан алгоритмыг Косаражу, Шарир нар 1980 оны орчимд бие даан санал болгосон. Энэ нь хоёр цуврал гүнзгийрүүлэх хайлт дээр суурилсан бөгөөд $O(n + m)$ ажиллах хугацаатай.

Алгоритмын эхний алхамд бид бүхэл графт зочилж цуврал гүнзгийрүүлэх хайлт (dfs) гүйцэтгэнэ. Өөрөөр хэлбэл зочлоогүй орой байсаар л бол бид тэдгээрийн нэгийг аваад, тэр оройноос гүнзгийрүүлэх хайлт эхлүүлнэ. Орой бүрийн хувьд бид гарах хугацаа $t_\text{out}[v]$-г хөтөлнө. Энэ нь орой $v$ дээрх dfs-ийн гүйцэтгэл дуусах 'цагийн тэмдэг', өөрөөр хэлбэл $v$-ээс хүрч болох бүх оройд зочилсон бөгөөд алгоритм $v$-д буцаж ирсэн мөч юм. Цагийн тэмдгийн тоолуурыг dfs-ийн дараалсан дуудалтуудын хооронд дахин тохируулах ёсгүй. Гарах хугацаа алгоритмд гол үүрэг гүйцэтгэх ба энэ нь дараах теоремыг авч үзэхэд тодорхой болно.

Эхлээд бид хүчтэй холбоост компонент $C$-ийн гарах хугацаа $t_\text{out}[C]$-г бүх $v \in C$-ийн хувьд $t_\text{out}[v]$ утгуудын максимум гэж тодорхойлно. Түүнчлэн теоремын баталгаанд бид орой $v\in G$ бүрийн орох хугацаа $t_{\text{in}}[v]$-г дурдана. $t_{\text{in}}[v]$ тоо нь алгоритмын эхний алхамд орой $v$ дээр рекурсив функц dfs дуудагдах 'цагийн тэмдэг'-ийг илэрхийлнэ. Хүчтэй холбоост компонент $C$-ийн хувьд бид $t_{\text{in}}[C]$-г бүх $v \in C$-ийн хувьд $t_{\text{in}}[v]$ утгуудын минимум гэж тодорхойлно.

Теорем

$C$ ба $C'$ нь хоёр өөр хүчтэй холбоост компонент байг, мөн конденсацийн графт $C$-ээс $C'$ хүрэх ирмэг байг. Тэгвэл $t_\text{out}[C] > t_\text{out}[C']$.

Баталгаа

Гүнзгийрүүлэх хайлт аль компонентод эхэлж хүрэхээс хамааран хоёр өөр тохиолдол байна:

  • Тохиолдол 1: компонент $C$-д эхэлж хүрсэн (өөрөөр хэлбэл $t_{\text{in}}[C] < t_{\text{in}}[C']$). Энэ тохиолдолд гүнзгийрүүлэх хайлт компонент $C$ ба $C'$-ийн бусад бүх оройд хараахан зочлоогүй байх ямар нэг мөчид ямар нэг орой $v \in C$-д зочилно. Конденсацийн графт $C$-ээс $C'$ хүрэх ирмэг байгаа тул $G$-д $v$-ээс $C$ дэх бусад бүх орой хүрэх боломжтой төдийгүй $C'$ дэх бүх орой ч бас хүрэх боломжтой. Энэ нь орой $v$-ээс ажиллаж буй энэ dfs гүйцэтгэл ирээдүйд компонент $C$ ба $C'$-ийн бусад бүх оройд ч бас зочлох болно гэсэн үг тул эдгээр орой нь гүнзгийрүүлэх хайлтын модонд $v$-ийн удам байх болно. Эндээс орой $u \in (C \cup C')\setminus \{v\}$ бүрийн хувьд $t_\text{out}[v] > t_\text{out}[u]$ байна гэдэг нь мөрдөнө. Тиймээс $t_\text{out}[C] > t_\text{out}[C']$ бөгөөд энэ нь баталгааны энэ тохиолдлыг дуусгана.

  • Тохиолдол 2: компонент $C'$-д эхэлж хүрсэн (өөрөөр хэлбэл $t_{\text{in}}[C] > t_{\text{in}}[C']$). Энэ тохиолдолд гүнзгийрүүлэх хайлт компонент $C$ ба $C'$-ийн бусад бүх оройд хараахан зочлоогүй байх ямар нэг мөчид ямар нэг орой $v \in C'$-д зочилно. Конденсацийн графт $C$-ээс $C'$ хүрэх ирмэг байгаа тул циклгүй байдлын шинж чанараар $C'$-ээс $C$ хүрэх боломжгүй. Иймд орой $v$-ээс ажиллаж буй dfs гүйцэтгэл $C$-ийн ямар ч оройд хүрэхгүй боловч $C'$-ийн бүх оройд зочилно. $C$-ийн оройнуудад алгоритмын энэ алхмын явцад хожим ямар нэг dfs гүйцэтгэл зочлох тул үнэхээр $t_\text{out}[C] > t_\text{out}[C']$ байна. Энэ нь баталгааг дуусгана.

Батлагдсан теорем нь хүчтэй холбоост компонент олоход маш чухал. Энэ нь конденсацийн граф дахь дурын ирмэг $t_\text{out}$-ийн их утгатай компонентоос бага утгатай компонент руу чиглэдэг гэсэн үг.

Хэрэв бид бүх орой $v \in V$-г гарах хугацаа $t_\text{out}[v]$-ийн буурах дарааллаар эрэмбэлбэл эхний орой $u$ нь конденсацийн графт орох ирмэггүй "үндэс" хүчтэй холбоост компонентод харьяалагдана. Одоо бид энэ орой $u$-ээс ямар нэг төрлийн хайлт ажиллуулж, тэр нь өөрийн хүчтэй холбоост компонент дахь бүх оройд зочлох боловч бусад оройд зочлохгүй байхыг хүсэж байна. Үүнийг давтан хийснээр бид бүх хүчтэй холбоост компонентыг аажмаар олж чадна: бид эхэлж олдсон компонентод харьяалагдах бүх оройг хасаад, дараа нь $t_\text{out}$-ийн хамгийн их утгатай үлдсэн дараагийн оройг олж, түүнээс энэ хайлтыг ажиллуулах гэх мэтчилэн. Эцэст нь бид бүх хүчтэй холбоост компонентыг олсон байх болно. Бидний хүссэнээр ажилладаг хайлтын аргыг олохын тулд бид дараах теоремыг авч үзнэ:

Теорем

$G^T$ нь $G$ дэх ирмэгийн чиглэлийг урвуулж авсан $G$-ийн шилжүүлсэн граф-ыг тэмдэглэе. Тэгвэл $\text{SCC}(G)=\text{SCC}(G^T)$. Түүнчлэн $G^T$-ийн конденсацийн граф нь $G$-ийн конденсацийн графыг шилжүүлсэн граф юм.

Баталгааг орхив (гэхдээ шууд ойлгомжтой). Энэ теоремын үр дүнд $G^T$-ийн конденсацийн графт "үндэс" компонентоос бусад компонент руу ирмэг байхгүй болно. Ингэснээр орой $v$-г агуулсан бүхэл "үндэс" хүчтэй холбоост компонентод зочлохын тулд бид шилжүүлсэн граф $G^T$-д орой $v$-ээс гүнзгийрүүлэх хайлт ажиллуулахад л хангалттай! Энэ нь яг энэ хүчтэй холбоост компонентын бүх оройд зочилно. Өмнө дурдсанчлан бид дараа нь эдгээр оройг графаас хасч болно. Дараа нь бид $t_\text{out}[v]$-ийн максимал утгатай дараагийн оройг олж, дараагийн хүчтэй холбоост компонентыг олохын тулд тэр оройноос эхлэн шилжүүлсэн графт хайлт ажиллуулна. Үүнийг давтан хийснээр бид бүх хүчтэй холбоост компонентыг олно.

Ингэснээр дүгнэвэл бид хүчтэй холбоост компонент олох дараах алгоритмыг авч үзлээ:

  • Алхам 1. $G$ дээр цуврал гүнзгийрүүлэх хайлт ажиллуул, энэ нь гарах хугацаа $t_\text{out}$-ийн өсөх дарааллаар эрэмбэлэгдсэн оройнуудын ямар нэг жагсаалтыг (жишээ нь order) өгнө.

  • Алхам 2. Транспонац граф $G^T$-г байгуулж, оройнууд дээр урвуу дарааллаар (өөрөөр хэлбэл гарах хугацааны буурах дарааллаар) цуврал гүнзгийрүүлэх хайлт ажиллуул. Гүнзгийрүүлэх хайлт бүр нэг хүчтэй холбоост компонентыг өгнө.

  • Алхам 3 (сонголтоор). Конденсацийн графыг байгуул.

Гүнзгийрүүлэх хайлтыг хоёр удаа гүйцэтгэдэг тул алгоритмын ажиллах хугацааны complexity нь $O(n + m)$ юм. Конденсацийн графыг байгуулах нь ч мөн $O(n+m)$.

Эцэст нь энд топологийн эрэмбэлэлт-ийг дурдах нь зүйтэй. 1-р алхамд бид оройнуудыг гарах хугацааны өсөх дарааллаар олно. Хэрэв $G$ циклгүй бол энэ нь $G$-ийн (урвуу) топологийн эрэмбэлэлтэд харгалзана. 2-р алхамд алгоритм хүчтэй холбоост компонентуудыг тэдгээрийн гарах хугацааны буурах дарааллаар олно. Ингэснээр энэ нь компонентуудыг — конденсацийн графын оройнуудыг — конденсацийн графын топологийн эрэмбэлэлтэд харгалзах дарааллаар олно.

Implementation

vector<bool> visited; // keeps track of which vertices are already visited

// runs depth first search starting at vertex v.
// each visited vertex is appended to the output vector when dfs leaves it.
void dfs(int v, vector<vector<int>> const& adj, vector<int> &output) {
    visited[v] = true;
    for (auto u : adj[v])
        if (!visited[u])
            dfs(u, adj, output);
    output.push_back(v);
}

// input: adj -- adjacency list of G
// output: components -- the strongy connected components in G
// output: adj_cond -- adjacency list of G^SCC (by root vertices)
void strongly_connected_components(vector<vector<int>> const& adj,
                                  vector<vector<int>> &components,
                                  vector<vector<int>> &adj_cond) {
    int n = adj.size();
    components.clear(), adj_cond.clear();

    vector<int> order; // will be a sorted list of G's vertices by exit time

    visited.assign(n, false);

    // first series of depth first searches
    for (int i = 0; i < n; i++)
        if (!visited[i])
            dfs(i, adj, order);

    // create adjacency list of G^T
    vector<vector<int>> adj_rev(n);
    for (int v = 0; v < n; v++)
        for (int u : adj[v])
            adj_rev[u].push_back(v);

    visited.assign(n, false);
    reverse(order.begin(), order.end());

    vector<int> roots(n, 0); // gives the root vertex of a vertex's SCC

    // second series of depth first searches
    for (auto v : order)
        if (!visited[v]) {
            std::vector<int> component;
            dfs(v, adj_rev, component);
            components.push_back(component);
            int root = *component.begin();
            for (auto u : component)
                roots[u] = root;
        }

    // add edges to condensation graph
    adj_cond.assign(n, {});
    for (int v = 0; v < n; v++)
        for (auto u : adj[v])
            if (roots[v] != roots[u])
                adj_cond[roots[v]].push_back(roots[u]);
}

The function dfs implements depth first search. It takes as input an adjacency list and a starting vertex. It also takes a reference to the vector output: each visited vertex will be appended to output when dfs leaves that vertex.

Note that we use the function dfs both in the first and second step of the algorithm. In the first step, we pass in the adjacency list of $G$, and during consecutive calls to dfs, we keep passing in the same 'output vector' order, so that eventually we obtain a list of vertices in increasing order of exit times. In the second step, we pass in the adjacency list of $G^T$, and in each call, we pass in an empty 'output vector' component, which will give us one strongly connected component at a time.

Тарьяны хүчтэй холбоост компонентын алгоритм

Алгоритмын тайлбар

Тайлбарласан алгоритмыг анх Тарьян 1972 онд санал болгосон. Энэ нь цуврал DFS дуудалт гүйцэтгэх, түүний бүтцэд угаас байдаг мэдээллийг ашиглан хүчтэй холбоост компонент (SCC)-ыг тодорхойлох дээр суурилсан бөгөөд $O(n+m)$ ажиллах хугацаатай.

Орой дээр DFS хэрэглэхдээ бид түүний зэргэлдээгийн жагсаалтыг тойрох ба зочлоогүй орой олдвол бид түүн дээр DFS-г рекурсивээр хэрэглэнэ.

Цуврал DFS дуудалтаар үүсгэгдсэн модыг авч үзье, үүнийг бид DFS мод гэж нэрлэнэ. Бид SCC-ийн орой дээр DFS-г анх дуудмагц түүний SCC-ийн бүх орой бие биендээ хүрч болох тул энэ дуудалт дуусахаас өмнө тэдгээрт зочилно. DFS модонд энэ эхний орой нь SCC-ийн бусад бүх оройн нийтлэг өвөг байх болно; бид энэ оройг SCC-ийн үндэс гэж тодорхойлно.

Теорем

SCC-ийн бүх орой DFS модны холбоост дэд графыг үүсгэнэ.

Баталгаа

Бид SCC-ийн бүх орой нийтлэг өвөгтэй буюу DFS дуудалтаар зочлох эхний оройтой болохыг тогтоосон. Орой $v$ ба түүний үндэс, орой $r$-г авч үзье. $r$-ээс $v$ хүрэх зам дахь бүх орой ижил SCC-д харьяалагдана. Эдгээр бүх оройд $r$-ээс хүрч болох ба тэд бүгд $v$-д хүрнэ, мөн тодорхойлолтоороо $v$ нь $r$-д хүрдэг тул эдгээр бүх орой бие биендээ хүрнэ. Үндэснээс SCC-ийн бусад орой бүр хүрэх бүх зам ижил SCC-д харьяалагдах тул үүссэн дэд граф холбоост байна.

SCC-үүд DFS модыг холбоост дэд графууд болгон төгс хуваадгийг анзаар.

Алгоритмын санаа дараах байдалтай:

  • Бид цуврал DFS дуудалт гүйцэтгэж, тэдгээрийг зэргэлдээгийн жагсаалтын оройнууд дээр рекурсивээр хэрэглэнэ.

  • Оройн зэргэлдээгийн жагсаалтыг тойрч дуусмагц бид ямар нэгэн байдлаар түүнийг үндэс мөн эсэхийг тодорхойлж чадна. Энэ аргыг хожим тайлбарлана.

  • Хэрэв орой нь үндэс бол бид дараа нь түүний SCC-ийн бүх оройг тэр даруй олж эзэмшинэ.

Бүх дуудалт дуусахад бүх үндэс илэрсэн байх ба бүх орой ямар нэг SCC-ийн хэсэг болгон эзэмшигдсэн байна.

Одоо энэ эзэмших процессыг нэвтрүүлэх үеийн DFS-ийн шинж чанарыг шинжилье.

Теорем

Орой $v$-г авч үзээд, бид түүний зэргэлдээгийн жагсаалтыг тойрч дөнгөж сая дууссан гэж үзье. Түүний дэд мод дахь эзэмшигдээгүй бүх орой ижил SCC-д харьяалагдана.

Баталгаа

Алгоритм SCC-ийн үндэс олдоход түүний оройнуудыг эзэмшинэ. $v$-ийн зэргэлдээгийн жагсаалтыг тойрсон тул түүний дэд мод дээрх бүх DFS дуудалт дууссан, үндсүүд илэрсэн, тэдгээрийн SCC-д харьяалагдах оройнууд эзэмшигдсэн байна. Үлдсэн эзэмшигдээгүй оройнуудын үндэс нь эзэмших процесс нь хараахан гүйцэтгэгдээгүй өвөг байх тул тэр нь эсвэл $v$, эсвэл $v$-ийн өвөг байна. $v$ нь бүх оройноос тэдгээрийн үндэс хүрэх замд байгаа бөгөөд SCC-үүд модны холбоост дэд графыг үүсгэх ёстой тул $v$ ба үлдсэн бүх орой хоёул ижил SCC-д харьяалагдана.

Теорем

Орой $v$-г авч үзээд, бид түүний зэргэлдээгийн жагсаалтыг тойрч, одоогоор ирмэг $(v, u)$-г боловсруулж байна гэж үзье. Хэрэв $u$-д ямар нэг DFS дуудалтаар аль хэдийн зочилсон бөгөөд эзэмшигдээгүй хэвээр байвал $v$ ба $u$ ижил SCC-д харьяалагдана.

Баталгаа

Ирмэгийн төрлөөс хамааран өөр өөр тохиолдол байна:

  • Модны ирмэг: хэрэв энэ нь модны ирмэг бол бид орой $u$-г анх удаа олж байна. Энэ нь бид эхлээд $u$ дээр DFS дуудалтыг рекурсивээр хэрэглэж, түүний DFS дуудалт дууссаны дараа түүнийг авч үзэх ёстой гэсэн үг. Хэрэв орой $u$ эзэмшигдээгүй хэвээр байвал түүний үндэс нь эсвэл $v$, эсвэл $v$-ийн өвөг тул тэдгээр ижил SCC-д харьяалагдах ёстой.

  • Буцах ирмэг: энэ бол илүү энгийн тохиолдол, хэрэв $u$ нь $v$-ийн өвөг бол тэдгээр бие биендээ хүрч болох ба тодорхойлолтоороо ижил SCC-д харьяалагдана.

  • Урагшлах ирмэг: энэ ирмэгийг боловсруулахаас өмнө $u$-ийн үндсийг олохгүйгээр дууссан цуврал DFS дуудалт байсан бөгөөд DFS дуудалт нь үргэлжилсэн $v$-д буцаж ирсэн. Тэгвэл $u$-ийн үндэс нь эзэмших процесс нь хараахан гүйцэтгэгдээгүй өвөг байх тул тэр нь эсвэл $v$, эсвэл $v$-ийн өвөг байх ба тиймээс тэдгээр ижил SCC-д харьяалагдах ёстой.

  • Хөндлөн ирмэг: үүнтэй адилаар энэ ирмэгийг боловсруулахаас өмнө $u$-ийн үндсийг олохгүйгээр дууссан цуврал DFS дуудалт байсан бөгөөд DFS дуудалт нь үргэлжилж, $v$ дээрх дуудалтад хүргэсэн шинэ цуврал DFS дуудалтыг эхлүүлсэн $u$ ба $v$-ийн нийтлэг өвөгт буцаж ирсэн. Тэгвэл $u$-ийн үндэс нь эзэмших процесс нь хараахан гүйцэтгэгдээгүй өвөг байх ба бүх боломжит нэр дэвшигчид $v$-тэй нийтлэг өвгүүд юм. $u$-ийн үндэс нь $v$-ийн өвөг тул тэр нь $v$-д хүрэх ба $v$ одоо $u$-д хүрдэг тул тэдгээр ижил SCC-д харьяалагдах ёстой.

Хоёр орой ижил компонентод харьяалагдах үед тэдгээрийн үндэс хоёулангийнх нь нийтлэг өвөг байх ёстойг анзаар.

Теорем

$v$ нь орой байг. Дараах мэдэгдлүүд эквивалент:

  1. $v$-ийн дэд мод дахь ямар нэг орой дэд модноос гадуурх эзэмшигдээгүй оройд хүрнэ.
  2. $v$ нь SCC-ийн үндэс биш.
Баталгаа

  • $1. \implies 2.$: $v$-ийн дэд мод дахь ямар нэг орой $u$ дэд модноос гадуурх эзэмшигдээгүй орой $w$-д хүрнэ гэж үзье. Бид $u$ ба $w$ ижил SCC-д харьяалагдах ба тэдгээрийн үндэс хоёулангийнх нь нийтлэг өвөг байх ёстойг тогтоосон. Энэ нийтлэг өвөг заавал дэд модноос гадна байх ба тэр нь мөн $v$-ийн өвөг байх болно. $v$ нь үндэснээс $u$ хүрэх замд байгаа тул тэр нь ижил SCC-д харьяалагдах ёстой бөгөөд түүний үндэс нь $v$ биш.

  • $\neg 1. \implies \neg 2.$: $v$-ийн дэд мод дахь ямар ч орой дэд модноос гадуурх эзэмшигдээгүй оройд хүрэхгүй гэж үзье. Энэ нь $v$-ийн дэд мод дахь ямар ч орой $v$-ийн өвөгт хүрэхгүй гэсэн үг байх ёстой. Дэд модноос гадуурх оройнууд руу очих цорын ганц боломжит ирмэг бол аль хэдийн эзэмшигдсэн оройнууд руу очих хөндлөн ирмэгүүд юм; эдгээр орой $v$-ийн өвөгт хүрч чадахгүй, учир нь хэрэв хүрсэн бол тэдгээр $v$-тэй ижил SCC-д харьяалагдах байсан бөгөөд тэдгээрийн SCC аль хэдийн тодорхойлогдсон тул энэ нь боломжгүй. $v$-ийн ямар ч өвөгт түүний дэд модноос хүрэх боломжгүй тул $v$-ийн үндэс нь $v$ өөрөө байх ёстой.

Одоо бид орой үндэс мөн эсэхийг тодорхойлох боломж олгодог аргыг олох ёстой бөгөөд эзэмших процессын шинж чанарууд түүний зөв байдалд зайлшгүй шаардлагатай. Үүний тулд бид орой $v \in G$ бүрийн хувьд $v$ дээр DFS дуудагдсан 'цагийн тэмдэг'-т харгалзах орох хугацаа $t_{in}[v]$-г тодорхойлно. Тодорхойлолтоороо үндэс нь SCC-ийн DFS-ээр зочлох эхний орой тул түүний SCC-ийн $t_{in}$-ийн минимал утгатай байна.

$v$ нь орой байг, мөн түүний дэд модыг авч үзье. Бид түүний зэргэлдээгийн жагсаалтыг тойрч дуусах мөчид дэд модноос гадуур DFS-ээр аль хэдийн зочилсон дурын орой $t_{in}$-ийн бага утгатай байна, учир нь DFS $v$ дээр эхлэхээс өмнө тэдгээр дээр анх дуудагдсан.

Эзэмших процессыг авч үзэхэд $v$-ийн дэд модноос гадуурх эзэмшигдээгүй бүх оройн $t_{in}$ утга нь $t_{in}[v]$-ээс бага байна. Одоо бид үндсийг тодорхойлохын тулд $t_{in}$-г хэрхэн ашиглахыг харж болно. Бид хүрч чадах эзэмшигдээгүй оройнуудын $t_{in}$-ийн минимал утгыг авч үзээд, энэ мэдээллийг модны ирмэгүүдээр өвгүүд рүү тараана. Тараасан утгыг бид $t_{low}$ гэж нэрлэнэ.

Илүү албан ёсоор бид $t_{low}[v]$-г $v$-ийн дэд мод дахь орой шууд ирмэгээр хүрч чадах $t_{in}$-ийн хамгийн бага утга гэж тодорхойлно. Тиймээс бид $t_{low}[v] < t_{in}[v]$ эсэхийг шалгаснаар орой $v$ үндэс мөн эсэхийг илрүүлж чадна.

Эцэст нь оройнуудыг эзэмшихийн тулд өөр графын тойролтын алгоритм гэх мэт олон арга байдаг боловч эзэмшигдээгүй оройнуудыг хөтлөхийн тулд энгийн өгөгдлийн бүтэц ашиглах ч бас боломжтой. Өгөгдлийн бүтцийг үндсэн зарчмаас тодорхойлохын тулд түүний хэрэгжүүлэх ёстой аргуудыг үзье, эдгээр нь ердөө хоёр:

  • Бид оройд анх зочлохдоо түүнийг өгөгдлийн бүтцэд зүгээр л оруулах ёстой, учир нь энэ орой эзэмшигдээгүй байна.

  • Бид үндэс олоход түүний дэд мод дахь үлдсэн бүх эзэмшигдээгүй оройг олж, тэдгээрийг өгөгдлийн бүтцээс хасах ёстой.

Орой $v$-ийн зэргэлдээгийн жагсаалтыг тойрсны дараа шууд $v$-ийн дараа өгөгдлийн бүтцэд байрлуулсан бүх орой түүний дэд модонд харьяалагддагийг анзаарснаар бид хасах үйлдлийг тайлбарлах өөр аргыг олж болно. Хэрэв $v$ нь үндэс бол $v$-ийн дараа оруулсан үлдсэн бүх оройг хасах ёстой. Тиймээс хасах үйлдлийг оронд нь дараах байдлаар тайлбарлаж болно:

  • Бид үндэс олоход түүний дараа оруулсан үлдсэн бүх оройг олж хасах ёстой.

Одоо бид үүнийг стекээр хэрэгжүүлж болохыг харж байна:

  • Бид оройд анх зочлохдоо түүнийг стек рүү түлхэнэ.

  • Бид үндэс олоход үндсийг өөрийг нь гаргаж авах хүртэл бүх элементийг гаргана.

Энэ нь эцэст нь бидэнд алгоритмыг хэрэгжүүлэх боломж олгоно.

Цуврал DFS дуудалтын ажиллах хугацааны complexity нь $O(n + m)$ юм. Стекийг авч үзвэл зангилаа бүрийг ердөө нэг удаа түлхэж, нэг удаа гаргадаг тул түүний complexity $O(n)$ болж хорогдоно. Тиймээс нийт ажиллах хугацааны complexity нь $O(n + m)$ байна.

Нэмэлт тэмдэглэл болгож хэлэхэд үндсүүд урвуу топологийн эрэмбээр олдоно. Алгоритмд орой нь түүний дэд модноос гадуурх эзэмшигдээгүй оройнууд руу ирмэггүй бол үндэс байх ба энэ нь бусад бүх хүрч болох компонент эсвэл түүний дэд модонд байна (тиймээс тэдгээрийн үндэс аль хэдийн олдсон), эсвэл тэдгээр нь дэд модноос гадуурх аль хэдийн эзэмшигдсэн оройнуудтай холбогдоно (тэдгээрийн үндэс ч мөн аль хэдийн олдсон) гэсэн үг. Тиймээс бүх хүрч болох компонент аль хэдийн олдсон байна, өөрөөр хэлбэл тэдгээр нь конденсацийн графын зөв урвуу топологийн эрэмбээр танилцуулагдана.

Implementation

vector<int> st;    // - stack holding the unclaimed vertices
vector<int> roots; // - keeps track of the SCC roots of the vertices
int timer;         // - dfs timestamp counter
vector<int> t_in;  // - keeps track of the dfs timestamp of the vertices
vector<int> t_low; // - keeps track of the lowest t_in of unclaimed vertices
                   // reachable in the subtree

// implements the tarjan algorithm for strongly connected components
void dfs(int v, vector<vector<int>> const &adj, vector<vector<int>> &components) {

  t_low[v] = t_in[v] = timer++;
  st.push_back(v);

  for (auto u : adj[v]) {
    if (t_in[u] == -1) { // tree-edge
      dfs(u, adj, components);
      t_low[v] = min(t_low[v], t_low[u]);
    } else if (roots[u] == -1) { // back-edge, cross-edge or forward-edge to an unclaimed vertex
      t_low[v] = min(t_low[v], t_in[u]);
    }
  }

  if (t_low[v] == t_in[v]) { // vertex is a root
    components.push_back({v}); // initializes a new component with root v
    while (true) {
      int u = st.back();
      st.pop_back();
      roots[u] = v; // claims the vertex
      if (u == v)
        break;
      components.back().push_back(u); // adds vertex u to the component of v
    }
  }
}

// input: adj -- adjacency list of G
// output: components -- the strongy connected components in G
// output: adj_cond -- adjacency list of G^SCC (by root vertices)
void strongly_connected_components(vector<vector<int>> const &adj,
                                   vector<vector<int>> &components,
                                   vector<vector<int>> &adj_cond) {
  components.clear();
  adj_cond.clear();

  int n = adj.size();

  st.clear();
  roots.assign(n, -1);
  timer = 0;
  t_in.assign(n, -1);
  t_low.assign(n, -1);

  // applies the tarjan algorithm to all the vertices
  // adds vertices to the components in reverse topological order
  for (int v = 0; v < n; v++) {
    if (t_in[v] == -1) {
      dfs(v, adj, components);
    }
  }

  // adds edges to the condensation graph
  adj_cond.assign(n, {});
  for (int v = 0; v < n; v++) {
    for (auto u : adj[v])
      if (roots[v] != roots[u])
        adj_cond[roots[v]].push_back(roots[u]);
  }
}

We have an accepted submission with this code in Library Checker.

As a last remark, there's an alternative way to iterate through the adjacency list. Currently, we are doing the following:

for (auto u : adj[v]) {
  if (t_in[u] == -1) { // tree-edge
    dfs(u, adj);
    t_low[v] = min(t_low[v], t_low[u]);
  } else if (roots[u] == -1) { // back-edge, cross-edge or forward-edge to an unclaimed vertex
    t_low[v] = min(t_low[v], t_in[u]);
  }
}

Alternatively, we could do:

for (auto u : adj[v]) {
  if (t_in[u] == -1) // vertex is not visited
    dfs(u, adj);
  if (roots[u] == -1) // vertex has not been claimed
    t_low[v] = min(t_low[v], t_low[u]);
}

$t_{low}$ is used to propagate the information to the root, and when we perform t_low[v] = min(t_low[v], t_in[u]), we know that $u$ and $v$ belong to the same SCC. If $t_{low}[u]$ is propagated until the root of $u$, it can also be propagated through $v$ since the root is the same. Since $t_{low}[u] \leq t_{in}[u]$, this does not introduce any conflicts, instead only improving the bound on the root of $v$.

Конденсацийн графыг байгуулах

When building the adjacency list of the condensation graph, we select the root of each component as the first vertex in its list of vertices (this is an arbitrary choice). This root vertex represents its entire SCC. For each vertex v, the value roots[v] indicates the root vertex of the SCC which v belongs to.

Our condensation graph is now given by the vertices components (one strongly connected component corresponds to one vertex in the condensation graph), and the adjacency list is given by adj_cond, using only the root vertices of the strongly connected components. Notice that we generate one edge from $C$ to $C'$ in $G^\text{SCC}$ for each edge from some $a\in C$ to some $b\in C'$ in $G$ (if $C\neq C'$). This implies that in our implementation, we can have multiple edges between two components in the condensation graph.

Ном зүй

  • Thomas Cormen, Charles Leiserson, Ronald Rivest, Clifford Stein. Introduction to Algorithms [2005].
  • M. Sharir. A strong-connectivity algorithm and its applications in data-flow analysis [1979].
  • Robert Tarjan. Depth-first search and linear graph algorithms [1972].

Дасгал бодлогууд