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

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

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

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

Алгоритм

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

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

  • $v=root$ гэсэн үлдсэн тохиолдлыг авч үзье. Энэ орой зөвхөн DFS модонд нэгээс олон хүүхэдтэй байх үед л зангилаа цэг байх болно.

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

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

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

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

Ингэснээр DFS мод дахь орой $v$ нь зөвхөн $low[to] \geq 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:

  • $visited[to] = false$ - the edge is part of DFS tree;
  • $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.

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++;
    int children=0;
    for (int to : adj[v]) {
        if (to == p) 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] && p!=-1)
                IS_CUTPOINT(v);
            ++children;
        }
    }
    if(p == -1 && children > 1)
        IS_CUTPOINT(v);
}

void find_cutpoints() {
    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_cutpoints; it performs necessary initialization and starts depth first search in each connected component of the graph.

Function IS_CUTPOINT(a) is some function that will process the fact that vertex $a$ is an articulation point, for example, print it (Caution that this can be called multiple times for a vertex).

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