cp algorithm articulation points

Solutions on MaxInterview for cp algorithm articulation points by the best coders in the world

showing results for - "cp algorithm articulation points"
Elisa
21 Nov 2017
1int n; // number of nodes
2vector<vector<int>> adj; // adjacency list of graph
3
4vector<bool> visited;
5vector<int> tin, low;
6int timer;
7
8void dfs(int v, int p = -1) {
9    visited[v] = true;
10    tin[v] = low[v] = timer++;
11    int children=0;
12    for (int to : adj[v]) {
13        if (to == p) continue;
14        if (visited[to]) {
15            low[v] = min(low[v], tin[to]);
16        } else {
17            dfs(to, v);
18            low[v] = min(low[v], low[to]);
19            if (low[to] >= tin[v] && p!=-1)
20                IS_CUTPOINT(v);
21            ++children;
22        }
23    }
24    if(p == -1 && children > 1)
25        IS_CUTPOINT(v);
26}
27
28void find_cutpoints() {
29    timer = 0;
30    visited.assign(n, false);
31    tin.assign(n, -1);
32    low.assign(n, -1);
33    for (int i = 0; i < n; ++i) {
34        if (!visited[i])
35            dfs (i);
36    }
37}
38