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

Графын гүүрийг $O(N+M)$-д олох

Бидэнд чиглэлгүй граф өгөгдсөн. Гүүр гэдэг нь хассан үед графыг холбоост биш болгодог (эсвэл илүү нарийвчлан хэлбэл граф дахь холбоост компонентын тоог ихэсгэдэг) ирмэг юм. Даалгавар бол өгөгдсөн граф дахь бүх гүүрийг олох явдал.

Албан бус хэлбэрээр бодлогыг дараах байдлаар томьёолно: замуудаар холбогдсон хотуудын газрын зураг өгөгдсөн бол бүх "чухал" замыг ол, өөрөөр хэлбэл хассан үед хотуудын ямар нэг хосын хоорондох зам алга болоход хүргэдэг замуудыг ол.

Энд тайлбарласан алгоритм гүнзгийрүүлэх хайлт дээр суурилах ба $O(N+M)$ complexity-тэй, энд $N$ нь графын оройн тоо, $M$ нь ирмэгийн тоо юм.

Гүүрийг онлайнаар олох өгүүлэл ч бас байгааг анхаарна уу — энд тайлбарласан офлайн алгоритмаас ялгаатай нь онлайн алгоритм нь өөрчлөгдөж буй граф дахь бүх гүүрийн жагсаалтыг хөтөлж чаддаг (өөрчлөлтийн цорын ганц төрөл нь шинэ ирмэг нэмэх явдал гэж үзвэл).

Алгоритм

Графын дурын орой $root$-г сонгоод түүнээс гүнзгийрүүлэх хайлт ажиллуул. Дараах баримтыг анхаарна уу (үүнийг батлахад амархан):

  • Бид DFS-д байгаа бөгөөд орой $v$-ээс эхлэх ирмэгүүдийг харж байна гэж хэлье. Одоогийн ирмэг $(v, to)$ нь зөвхөн DFS тойролтын мод дахь $to$ орой ба түүний удмуудын аль нь ч орой $v$ эсвэл түүний ямар ч өвөг рүү буцах ирмэггүй үед л гүүр болно. Үнэндээ энэ нөхцөл нь $v$-ээс $to$ хүрэх ирмэг $(v, to)$-ээс өөр зам байхгүй гэсэн үг.

Одоо бид энэ баримтыг орой бүрийн хувьд үр ашигтай шалгаж сурах ёстой. Бид гүнзгийрүүлэх хайлтаар тооцоолсон "зангилаанд орох хугацаа"-г ашиглана.

Тэгэхээр $\mathtt{tin}[v]$ нь зангилаа $v$-ийн орох хугацааг тэмдэглэе. Бид $\mathtt{low}$ массивыг танилцуулах бөгөөд энэ нь зангилаа $v$ өөрөөсөө эсвэл удмуудаасаа нэг ирмэгээр хүрч чадах, DFS хайлтаар олдсон зангилааны хамгийн эрт орох хугацааг хадгалах боломж олгоно. $\mathtt{low}[v]$ нь $\mathtt{tin}[v]$, зангилаа $v$-тэй буцах ирмэг $(v, p)$-ээр холбогдсон зангилаа $p$ бүрийн орох хугацаа $\mathtt{tin}[p]$, мөн DFS модонд $v$-ийн шууд удам болох орой $to$ бүрийн $\mathtt{low}[to]$ утгуудын хамгийн бага нь юм:

$$\mathtt{low}[v] = \min \left\{ \begin{array}{l} \mathtt{tin}[v] \\ \mathtt{tin}[p] &\text{ for all }p\text{ for which }(v, p)\text{ is a back edge} \\ \mathtt{low}[to] &\text{ for all }to\text{ for which }(v, to)\text{ is a tree edge} \end{array} \right\}$$

Одоо орой $v$ эсвэл түүний удмуудын нэгээс түүний өвгүүдийн нэг рүү буцах ирмэг байх нь зөвхөн орой $v$ нь $\mathtt{low}[to] \leq \mathtt{tin}[v]$ байх хүүхэд $to$-тэй байх үед л биелнэ. Хэрэв $\mathtt{low}[to] = \mathtt{tin}[v]$ бол буцах ирмэг шууд $v$ рүү ирнэ, эс бөгөөс $v$-ийн өвгүүдийн нэг рүү ирнэ.

Ингэснээр DFS мод дахь одоогийн ирмэг $(v, to)$ нь зөвхөн $\mathtt{low}[to] > \mathtt{tin}[v]$ байх үед л гүүр болно.

Implementation

The implementation needs to distinguish three cases: when we go down the edge in DFS tree, when we find a back edge to an ancestor of the vertex and when we return to a parent of the vertex. These are the cases:

  • $\mathtt{visited}[to] = false$ - the edge is part of DFS tree;
  • $\mathtt{visited}[to] = true$ && $to \neq parent$ - the edge is back edge to one of the ancestors;
  • $to = parent$ - the edge leads back to parent in DFS tree.

To implement this, we need a depth first search function which accepts the parent vertex of the current node.

For the cases of multiple edges, we need to be careful when ignoring the edge from the parent. To solve this issue, we can add a flag parent_skipped which will ensure we only skip the parent once.

void IS_BRIDGE(int v,int to); // some function to process the found bridge
int n; // number of nodes
vector<vector<int>> adj; // adjacency list of graph

vector<bool> visited;
vector<int> tin, low;
int timer;

void dfs(int v, int p = -1) {
    visited[v] = true;
    tin[v] = low[v] = timer++;
    bool parent_skipped = false;
    for (int to : adj[v]) {
        if (to == p && !parent_skipped) {
            parent_skipped = true;
            continue;
        }
        if (visited[to]) {
            low[v] = min(low[v], tin[to]);
        } else {
            dfs(to, v);
            low[v] = min(low[v], low[to]);
            if (low[to] > tin[v])
                IS_BRIDGE(v, to);
        }
    }
}

void find_bridges() {
    timer = 0;
    visited.assign(n, false);
    tin.assign(n, -1);
    low.assign(n, -1);
    for (int i = 0; i < n; ++i) {
        if (!visited[i])
            dfs(i);
    }
}

Main function is find_bridges; it performs necessary initialization and starts depth first search in each connected component of the graph.

Function IS_BRIDGE(a, b) is some function that will process the fact that edge $(a, b)$ is a bridge, for example, print it.

Note that this implementation malfunctions if the graph has multiple edges, since it ignores them. Of course, multiple edges will never be a part of the answer, so IS_BRIDGE can check additionally that the reported bridge is not a multiple edge. Alternatively it's possible to pass to dfs the index of the edge used to enter the vertex instead of the parent vertex (and store the indices of all vertices).

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