Articulation Points and Bridges

Articulation Points and Bridges

In this article, we shall learn about articulation points and bridges. If in a connected graph, the removal of a node makes the graph disconnected, the node is said to be an articulation point. Similarly, If in a connected graph, the removal of an edge makes the graph disconnected, the edge is said to be a bridge.

What is an Articulation Point?

Suppose in a graph ‘G’, there is a node ‘u’ having ‘c’ connected components. u will be an articulation point if eliminating it as well as its edges, increments the total number of connected components in G. A brute force way of finding articulation points is in O(V * (V + E)). It is:

For every node u in the graph G do:
    Remove u from G
    u is an articulation point if the number of connected components have increased
    Add u back to G

Tarjan's approach

We first must find each node ‘a’ that is an ancestor to a node ‘u’  and was found before u in a DFS. Suppose there is a node ‘v’ that we can reach from u through some intermediate nodes in a DFS. If v is also accessible from a without having to pass through u, then u is not an articulation point, since, on the removal of u from G, v is still accessible from a.

Following are the 2 conditions for u to be an articulation point:

  • If each path from a to v has u in it.
  • If u is the root of the DFS having a minimum of 2 children subgraphs that are disconnected from each other.

We may decompose the condition 1st into the following 2 sub-conditions for u to be an articulation point:

  • u does not have any adjacent node v that can reach a without ever visiting u.
  • u is the root of some cycle in the DFS.


Examples:


‘B’ is an articulation point as each path from ancestors of B to ‘C’ have B in them.


B is not an articulation point as there are some paths from ancestors of B to C that does not have B in them.


B is an articulation point as it has a minimum of two children subgraphs that are disconnected from each other.

Implementation

#include "iostream"
#include "vector"
#include "limits.h"
#include "math.h"
#include "algorithm"
#include "functional"
#include "numeric"

using namespace std;

vector<vector<int>>g;

void dfsMod(int u, vector<int>& dfn, vector<int>& low, vector<int>& par, vector<int>& cutVertices, vector<int>& vis, int& time){
    int childrenU = 0;
    vis[u] = 1;
    low[u] = dfn[u] = time++;   
    for(int child : g[u]){
        if(dfn[child] == -1){
            par[child] = u;
            childrenU++;
            dfsMod(child, dfn, low, par, cutVertices, vis, time);
            low[u] = min(low[u], low[child]);           
            if (par[u] == -1 && childrenU > 1){
 cutVertices[u] = 1;
 }
 else if (par[u] != -1 && low[child] >= dfn[u]){
 cutVertices[u] = 1;
 }
        }
        else if(par[u] != child){
            low[u] = min(low[u], dfn[child]);
        }
    }
}

void findAps(int n, int e){
    vector<int>par(n+1, -1), dfn(n+1, -1), low(n+1, -1), cutVertices(n + 1), vis(n+1);
 int con = 1, ap = 0, time = 1;
 for (int i = 0; i < n; ++i){
 if (dfn[i] == -1){
 dfsMod(i, dfn, low, par, cutVertices, vis, time);
 time = 1;
 }
 }
 for(int i = 0;i < n;i++){
        if(!vis[i]){
            cout << "The graph is disconnected!";
            con = 0;
        }
        ap+=(cutVertices[i]==1);
    }
    if(ap){
        cout<<"The graph has articulation points:"<<endl;       
    for(int i = 0;i < n;i++){
            if (cutVertices[i] == 1){
    cout<<i<<' ';
    }
    }
    }
}

int main(){
    int n, e;
    cin>>n>>e;
    g.resize(n);
    for(int i=0;i<e;++i){
        int u, v;
        cin>>u>>v;
        g[u].push_back(v), g[v].push_back(u);
    }
    findAps(n, e);
}

Input

6 7
0 1
1 2
2 0
3 4
4 5
5 3
2 3

Output

The graph has articulation points:
2 3 

write your code here: Coding Playground

What are bridges?

Suppose, there is an edge ‘e’ (= {u,v}) in G. The edge e will be a bridge if eliminating it, increments the total number of connected components in G. The concept and implementation of finding bridges are the same as that of finding articulation points from above. The difference is that the condition for e to be a bridge is: discoveryTime[u] < low[v] instead of discoveryTime[u] <= low[v].

Implementation

#include "iostream"
#include "vector"
#include "limits.h"
#include "math.h"
#include "algorithm"
#include "functional"
#include "numeric"
#include "iomanip"

using namespace std;

class tarjan{
public:
    int n, time;
    vector<bool>vis;
    vector<int>disc, low;
    vector<vector<int>>bridges;
    void dfsBridges(const vector<vector<int>>&g, int nd, int par) {
        vis[nd] = 1;
        disc[nd] = low[nd] = time++;
        for (int child : g[nd]) {
            if (child == par){
                continue;
            }
            if (vis[child]) {
                low[nd] = min(low[nd], disc[child]);
            }
            else {
                dfsBridges(g, child, nd);
                low[nd] = min(low[nd], low[child]);
                if (low[child] > disc[nd]){
                    bridges.push_back({nd, child});
                }
            }
        }
    }
    void tarjanBridges(const vector<vector<int>>&g) {
        time = 0, n=g.size();
        vis.assign(n, 0), disc.assign(n, -1), low.assign(n, -1);
        for (int i = 0; i < n; ++i) {
            if (!vis[i]){
                dfsBridges(g, i, -1);
            }
        }
    }
};

int main(){
    int n, e;
    cin>>n>>e;
    tarjan t;
    vector<vector<int>>g(n);
    for(int i=0;i<e;++i){
        int u,v;
        cin>>u>>v;
        g[u].push_back(v), g[v].push_back(u);
    }
    t.tarjanBridges(g);
    for(auto it:t.bridges){
        for(auto ti:it){
            cout<<ti<<' ';
        }
        cout<<endl;
    }
    return 0;
}

Input

6 7
0 1 1 2 2 0 3 4 4 5 5 3 2 3

Output

2 3 

write your code here: Coding Playground