Articulation points, bridges, and Strong Connected Components

Articulation points and Bridges (undirected graph)

Articulation points

Articulation points are nodes in the undirected graph which if removed from the graph also disconnects the graph.

In the above graph, removing node 1 disconnects graph into two components therefore 1 is an articulation point.

Articulation bridge

Articulation edges are edges in the undirected graph which if removed from the graph also disconnect the graph.

In above graph, removing edge <1,3> disconnects the graph therefore <1,3> is a articulation bridge.

Bruteforce approach to find out ariticulation points or bridges

1. Run a regular DFS or BFS to find out the number of components in the graph.
2. For each node, first remove it and try to find out a number of components again. If it is not same as before the removal of node then this node is a articulation point.
3. To find out the articulation bridge, run the same above #2 step for each edges to find out the bridge.
4. Time complexity of bruteforce approach is O(V*(E+V) for articulation points and O(E*(E+V) for bridge.

But we can use the Tarjan algorithm to find out the articulation point and bridge using regular dfs in order O(V+E).

Tarjan algorithm

1. Capture arrival time arrivalfor each node. This stores the iteration counter when the vertex is visited for the first time.
2. For each node, we just need to maintain two state UNVISITED and VISITED .
3. We can initialize arrival time as 0 and if the value is 0 then we can mark it as UNVISITED otherwise VISITED. This will avoid introducing separate storage to track the visited/unvisited nodes.
4. We also need to capture the lowest arrival time for each node.
5. Lowest arrival lowest_arrivaltime is captured by following.

a. If R vertices in DFS spanning subtree rooted at u (including u)

b. lowest_arrival[u] stores the lowest arrival time in R .

c. lowest_arrival[u] is updated by arrival[v]of a vertex not in R that is reachable by a back edge.

d. Initially, lowest_arrival[u] = arrival[u] .

e. Later, lowest_arrival[u] can only be made smaller if DFS encounters a back edge that connects a vertex u in R to another vertex v not in R that has lower arrival[v] .

f. We do not update lowest_arrival[u] if edge <u,v> is a bidirectional edge.

Without cycle

Above is an example of the graph without back edge (i.e. cycle). Here lowest_arrival[x] = arrival[x] . A sequence of visitation is 0->1 -> 2 (backtrack to 1) -> 4 -> 3 (backtrack to 4) -> 5 . As there is no back edge therefore lowest_arrival[x] = arrival[x] for all the nodes.

Graph with cycle i.e. back edge

The sequence of visitation is 0->1->2 (backtrack to 1) -> 3 (backtrack to 1)-> 4 -> 5 . In the DFS spanning tree, there is an important back edge that forms a cycle. i.e. edge 5->1 .

This causes vertex 1 (itself) , 4 (indirectly) , 5( back edge) to all able to reach the vertex 1 with arrival[1] . So we can update loest_arrival for all these vertices {1,4,5} as 1 .

Identify an articulation vertex

u is an articulation point if the following relationship is valid for it’s neighbor v

lowest_arrival[v] >= arrival[u]

1. This is because the fact that lowest_arrival[v] is greater than arrival[u] implies that there is no back edge from a vertex in the subtree rooted at v that can reach another vertex w with a lower arrival[w] than arrival[u] .
2. A vertex w with lowest_arrival[w] than vertex u with arrival[u] implies that w is the ancestor of u in the DFS spanning tree. This means that to reach the ancestor of u from v , one must pass through the critical articulation point vertex u.
3. The root of DFS spanning tree is a special case. The root is an articulation point only if it has more than one child in the DFS spanning tree.
4. Root special case is only for articulation point, not for bridge.

Identify an articulation bridge

Edge u->v is a bridge if the following condition satisfied.

lowest_arrival[v] > arrival[u]

Note: Equal sign is removed compared to articulation point.

Following is the code to implement the Tarjan algorithm.

const solve = (graph) => {
  const n = graph.length;
  const arrival = [];
  const lowest_arrival = [];
  const parent = [];
  const articulation_vertex = [];
  const articulation_bridge = [];
  let counter = 0;
  let root;
  let rootChildren = 0;
  const articulationPointAndBridge = u => {
    arrival[u] = ++counter;
    lowest_arrival[u] = arrival[u];
    for (const [v,w] of graph[u]) {
      if(!arrival[v]) {
          parent[v] = u;
          if(u === root) {
            rootChildren++;
          }
          articulationPointAndBridge(v);
          // For articulation point
          if(lowest_arrival[v] >= arrival[u]) {
             articulation_vertex.push(u);
          }
          // For articulation bridge
          if(lowest_arrival[v] > arrival[u]) {
              articulation_bridge.push([u,v]);
          }
          // Update lowest arrival time
          lowest_arrival[u] = Math.min(lowest_arrival[u], lowest_arrival[v]);
      } else if( v !== parent[u] ) {
          // Upate lowest arrival time for cycle
          lowest_arrival[u] = Math.min(lowest_arrival[u], arrival[v]);
      }
    }
  }
  for (let u=0; u < n; u++) {
    if(!arrival[u]) { // UNVISITED
      root = u;
      rootChildren = 0;
      articulationPointAndBridge(u);
      articulation_vertex[root] = rootChildren > 1; // Special case
    }
  }
}

Now let’s solve leetcode problem based on articulation points/bridges

1192. Critical Connections in a Network

https://leetcode.com/problems/critical-connections-in-a-network/description/

The goal here is to find out the critical connection in the given undirected server-to-server network. Which is equal to finding the Articulation bridges. Following is the code to implement Tarjan’s algorithm to find out the articulation bridges.

Note: No need to apply root check here.

const buildGraph = (n, connections) => {
    const graph = new Array(n).fill(0).map(a => []);
    for (const [u, v] of connections) {
        graph[u].push(v);
        graph[v].push(u);
    }
    return graph;
}
/**
 * @param {number} n
 * @param {number[][]} connections
 * @return {number[][]}
 */
var criticalConnections = function (n, connections) {
    const graph = buildGraph(n, connections);
    const arrival = new Array(n).fill(0);
    const lowestArrival = new Array(n).fill(0);
    const parent = new Array(n).fill(null);
    const ans = [];
    let counter = 0;
    const articulationBridge = (u) => {
        arrival[u] = ++counter;
        lowestArrival[u] = arrival[u];
        for (const v of graph[u]) {
            if (!arrival[v]) { // UNVISITED
                parent[v] = u;
                articulationBridge(v);
                // Check for bridge condition
                if (lowestArrival[v] > arrival[u]) {
                    ans.push([u, v]);
                }
                // Update lowest arrival
                lowestArrival[u] = Math.min(lowestArrival[u], lowestArrival[v]);
            } else if (parent[u] !== v) { // Cycle check
                lowestArrival[u] = Math.min(lowestArrival[u], arrival[v]);
            }
        }
    }
    // Try all possible roots
    for (let u = 0; u < n; u++) {
        if (!arrival[u]) {
            articulationBridge(u);
        }
    }

    return ans;
};

1568. Minimum Number of Days to Disconnect Island

https://leetcode.com/problems/minimum-number-of-days-to-disconnect-island/description/

1. We have given the grid to represent the land as cell value 1 and water as cell value 0
2. We need to find out the number of nodes that can be deleted to disconnect the island.

Key intuition to solve this problem.

1. Deleting one node to disconnect the graph is standard algorithm called Articulation point.
2. But in this problem we can delete more than one nodes to disconnect the graph which makes it difficult.
3. Suprisingly, since input is given as grid therefore at max we just need to delete two nodes to disconnect the graph. How? To understand let’s see following example. As you see, you can always delete any two nodes from corner to disconnect the graph.

No matter how big or small graph is, we can always delete max two nodes from corner to disconnect the graph.

Based on this intuition, we can come up with following approach.

Approach 1: Bruteforce

1. Find out the number of connected components in the graph, if it is greater than one or zero then return zero. I.e. graph is already disconnected to so no need to delete any nodes.
2. Try each node and run the regular dfs to find out the number of connected components again, if it changed then return 1 .
3. If none of the nodes on removal can reduce the connected components then return 2 .

Approach 2: Use Tarjan algorithm to find out Articulation point

1. Find out the number of connected components in the graph, if it is greater than one or zero then return zero. I.e. graph is already disconnected to so no need to delete any nodes.
2. Run articulation point algorithm on the graph which has just one connected component. If it returns at least one node then return 1 as answer.
3. Otherwise simply return hardcoded 2

Following is code to implement this approach.

/**
 * @param {number[][]} grid
 * @return {number}
 */
var minDays = function (grid) {
    const m = grid.length;
    const n = grid[0].length;
    const arrival = new Array(m * n).fill(0);
    const lowest = new Array(m * n).fill(0);
    const parent = new Array(m * n).fill(-1);
    const getNode = (i, j) => n * i + j;

    let articulations = 0;
    let components = 0;
    let counter = 0;
    let rootChildren = 0;
    let root;
    const getNeighbors = (i, j) => {
        const neighbors = [];
        const dirs = [[-1, 0], [1, 0], [0, -1], [0, 1]];
        for (const [p, q] of dirs) {
            const x = p + i;
            const y = q + j;
            if (x >= 0 && x < m && y >= 0 && y < n && grid[x][y]) {
                neighbors.push([x, y]);
            }
        }
        return neighbors;
    }
    const articulationPoint = (i, j) => {
        const u = getNode(i, j);
        arrival[u] = ++counter;
        lowest[u] = arrival[u];

        for (const [x, y] of getNeighbors(i, j)) {
            const v = getNode(x, y);
            if (!arrival[v]) { // UNVISITED
                parent[v] = u;
                if (u === root) {
                    rootChildren++;
                }
                articulationPoint(x, y);

                // Check for articulation point
                if (u !== root && lowest[v] >= arrival[u]) {
                    articulations++;
                }
                // Update lowest arrival
                lowest[u] = Math.min(lowest[u], lowest[v]);
            } else if (parent[u] !== v) { // Cycle check
                lowest[u] = Math.min(lowest[u], arrival[v]);
            }
        }
    }
    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            if (grid[i][j] && !arrival[getNode(i, j)]) { // Launch dfs for unvisited and land
                components++;
                root = getNode(i, j);
                rootChildren = 0;
                articulationPoint(i, j);
                articulations += (rootChildren > 1 || rootChildren === 0 ? 1 : 0); // Special caes for root
            }
        }
    }

    if (components > 1 || components === 0) {
        return 0;
    }
    if (components === 1) {
        return articulations > 0 ? 1 : 2;
    }
};

Please note; two extra modifications are done in the articulation points calculation.

1. If there is just single 1 cell in the grid, then articulation point doesn’t detect it. Therefore had to handled it during root node.
2. During articulation point calculation skip it for the root node.

928. Minimize Malware Spread II

https://leetcode.com/problems/minimize-malware-spread-ii/description/

1. Network of n nodes.
2. Edge is represented by n*n matrix if graph[i][j] ==1
3. Set of nodes initial are given as already infected.
4. After spreading infection M(initial) is the number of infected nodes.
5. We need to remove exactly one node from initial .
6. Return the node that, if removed, would minimize M(initial)

Following are intuition to solve this problem.

1. If we remove A then all the sub graph for it’s neighbor for example P , has two cases.

Case a: There is at least one node from initial, if it is then all the nodes in this sub graph will get infected anyway.

Case b: There is no nodes from initial, then none of these nodes will be infected.

2. Goal is to find out the number of unaffected nodes in the each child subgraph of removed node A . I.e. sum of unaffected nodes for each children.

3. Keep track of unaffected nodes for each node to find out the maximum number of unaffected nodes on removing that node.

4. Maximum number of unaffected nodes in the child subgraph will minimize the M(initial) on removal of node A .

5. Keep track of node A which will give the max value will be the answer node.

Approach 1: Bruteforce to apply dfs

1. Iterate each node A in initial set.
2. Run dfs on each neighbor of A and get the total count of not infected nodes.
3. Keep track of node which maximize the not infected nodes.

Q. How to remove node from graph?

Ans. Simply mark it as visited so that dfs will not pick this node for traversal.

Time complexity: O(K* N^2) where N = number of total nodes and K = number of initially infected nodes.

Approach 1: Use Tarjan’s Articulation point algorithm

1. Run Articulation point algorithm to find out all the articulation points.
2. During Articulation point algorithm, it also tells us which DFS subtree would get disconnected from the graph if we were to remove this node.
3. We can use this information to solve our problem.
4. If that subtree does not contain any other initially infected nodes, then it is clear that removing this node is going to save that entire subtree otherwise it doesn’t matter.
5. It means, we need to do extra (apart from the usual stuff for Tarjan’s algo) is to make DFS method return the size of the connected component when there are no infected nodes in it otherwise 0.

Followig is code to implement this approach.

/**
 * @param {number[][]} graph
 * @param {number[]} initial
 * @return {number}
 */
var minMalwareSpread = function (graph, initial) {
    const n = graph.length;
    const arrival = new Array(n).fill(0);
    const lowest = new Array(n).fill(0);
    const parent = new Array(n).fill(-1);
    const size = new Array(n).fill(0);
    let ans = initial[0]; // Initialize with first
    let max = 0;
    const infected = new Set(initial);
    let counter = 0;
    const getNeighbors = u => {
        const neighbors = [];
        for (let v = 0; v < n; v++) {
            if (graph[u][v]) {
                neighbors.push(v);
            }
        }
        return neighbors;
    }

    const dfs = u => { // post order traversal to get the count
        arrival[u] = ++counter;
        lowest[u] = arrival[u];
        let count = 1;
        let isInfected = infected.has(u);
        for (const v of getNeighbors(u)) {
            if (!arrival[v]) { // UNVISITED
                parent[v] = u;
                const s = dfs(v);
                if (s === 0) { // It means found infected node in the subgraph
                    isInfected = true;
                } else {
                    count += s;
                }
                // Articulation point test for u
                if (lowest[v] >= arrival[u]) {
                    size[u] += s; // accumulate for each disconnected graph
                }
                lowest[u] = Math.min(lowest[u], lowest[v]);
            } else if (parent[u] !== v) {
                lowest[u] = Math.min(lowest[u], arrival[v]);
            }
        }
        return isInfected ? 0 : count;
    }
    for (const u of initial) {
        if (!arrival[u]) { // UNVISITED
            dfs(u);
        }
        // Update global ans
        if (size[u] > max || size[u] === max && u < ans) {
            max = size[u];
            ans = u;
        }
    }
    return ans;
};

Strongly connected components (Directed Graph)

1. Running dfs(0) will reach all the nodes of the above graph.
2. This means the above graph has only one connected component.
3. But it is not a SCC. For example node 1 can’t reach to node 0 .
4. SCC is a set of nodes, if we pick any pair of vertices u and v in the SCC, we can find a path from u and v and vice versa.
5. In the above graph, there are three SCC as{0}, {1,2,3} and {4, 5, 6, 7}

Kosaraju’s algorithm to find out SCC

To understand Kosaraju’s algorithm, we need to do two observations.

1. Running dfs(u) on a directed graph where u is part of its smallest SCC and will only visit vertices in the smallest SCC. For example, if we run dfs(4) on the above graph, we can only visit {4,5,6,7} . But if we run dfs(3) we will reach vertices {1,2,3} as well as {4,5,6,7} . This is due to edge {3->4} that caused this leakage. The question here is how to find the smallest SCC.
2. SCC of the original directed graph and the SCC of the transpose graph are identical. Following is a transpose graph for the same graph that shows identical SCC.

Kosaraju’s algorithm combines these two ideas as below.

1. Run dfs() the post-order flavor on the original directed graph and record the explored vertices in decreasing finishing order. For example on the above graph running dfs(0)it would be {0, 1, 3, 4, 5, 7, 6, 2}.
2. Running dfs(0) on the same transposed graph we immediately get stuck hence we found our first smallest SCC {0} . If we then proceed with dfs(1), it will give the next SCC as {1,2,3}. Finally with dfs(4) will get {4,5,6,7}.

Note: The finishing order found in step#1 must be used as the order for step#2 to avoid leakage.

Following is the code to implement this algorithm.

const solve = (graph) {
  const tranpose_graph = buildTransposeGraph();
  const n = graph.length;
  const sequence = [];
  const arrival = new Array(n).fill(0);
  let counter = 0;
  const kosaraju = (u, pass) => {
    arrival[u] = ++counter;
    const neighbors = pass === 1 ? graph[u] : tranpose_graph[u];
    for (const v of neighbors) {
      if(!arrival[v]) {
        kosaraju(v, pass);
      }
    }
    sequence.push(u); // Build sequence
  }
  // Pass 1: Find dfs traversal sequence
  for (let u=0; u < n; u++) {
    if(!arrival[u]) { // UNVISITED
      kosaraju(u,1);
    }
  }
  // Pass 2: Run SCC on transpose graph as per traversal sequence order
  let ans = 0;
  arrival.size = 0; // reset arrival time
  for (let i= n-1; i>=0; i--) {
    const u = sequence[i];
    if(!arrival[u]) {
      ans++;
      kosaraju(u, 2);
    }

  }
  return ans;
}

Tarjan algorithm to find out SCC

The basic idea of Tarjan’s algorithm to find out SCC is

1. SCC form subtrees in the DFS spanning tree.
2. Along with computing arrival[u] and lowest_arrival[u] we also maintain the stack to keep track of visited node.
3. Update lowest_arrival only when a vertex is visited. This approach is different compared to articulation point/bridge calculations.
4. Now if lowest_arrival[u]=arrival[u],we can conclude that u is the root of an SCC.
5. Member of this SCC is identified by popping the current content of the stack S until we reach the vertex u again.

Following is the code to implement this algorithm.

const solve = graph => {
  const n = graph.length;
  const arrival = new Array(n).fill(0);
  const lowestArrival = new Array(n).fill(0);
  const visited = new Array(n).fill(0);
  const stack = [];
  let counter = 0;
  let sccCount = 0;
  const tarjanSCC = u=> {
    arrival[u] = ++counter;
    lowestArrival[u] = arrival[u];
    stack.push(u);
    visited[u] = 1;
    for (const [v,w] of graph[u]) {
      if(!arrival[v]) {
        tarjanSCC(v);
      }
      if(visited[v]) { // cycle condition
        lowestArrival[u] = Math.min(lowestArrival[u], arrival[v]);
      }
    }
    // Check for SCC for each node u
    if(lowestArrival[u] == arrival[u]) {
        sccCount++;
        while(true) {
          const v = stack.pop();
          visited[v] = 0; // Undo visited state
          if(u === v) {
              break;
          }
        }
    }
    
  }
  for (let u=0; u < n; u++) {
      if(!arrival[u]) {
          tarjanSCC(u);
      }
  }
  
}

Let’s solve few problem related to SCC.

2360. Longest Cycle in a Graph

https://leetcode.com/problems/longest-cycle-in-a-graph/description/

For the given directed graph, find out the length of the longest cycle.

Approach 1: Detect the cycle and count the length

We can run a regular cycle detection algorithm on the directed graph and every time we find a cycle, we can calculate the cycle length and update the global answer.

The time complexity of this code would be T((V+E)*V) ~ T(n*n) . Following is the code to implement this approach.

/**
 * @param {number[]} edges
 * @return {number}
 */
var longestCycle = function (edges) {
    const n = edges.length;
    const visited = new Array(n).fill(0); // 0: unvisited, 1: explored, 2: visited
    const parent = new Array(n).fill(-1);
    let ans = 0;
    const dfs = u => {
        visited[u] = 1;
        const v = edges[u];
        // process unvisited v
        if (v !== -1) {
            if (!visited[v]) {
                parent[v] = u;
                dfs(v);
            } else if (visited[v] === 1) { // Already explored i.e. back edge
                // This is a condition for cycle, find the size
                let count = 1;
                let x = u;
                while (x !== v) {
                    count++;
                    x = parent[x];
                }
                // update global ans
                ans = Math.max(ans, count);
            }
        }
        visited[u] = 2;
    }
    for (let i = 0; i < n; i++) {
        if (!visited[i]) {
            console.log({ root: i })
            dfs(i);
        }
    }
    return ans === 0 ? -1 : ans;
};

Approach 2: Using SCC with the help of Kosaraju’s algorithm

/**
 * @param {number[]} edges
 * @return {number}
 */
var longestCycle = function (edges) {
    const n = edges.length;
    const transpose = new Array(n).fill(0).map(a => []);
    for (let u = 0; u < n; u++) {
        const v = edges[u];
        if (v !== -1) {
            transpose[v].push(u);
        }
    }
    const arrival = new Array(n).fill(0);
    let timer = 0;
    const sequence = [];
    let ans = 0;
    const pass1 = u => { // run dfs on orginal graph
        arrival[u] = ++timer;
        const v = edges[u];
        if (v != -1) {
            if (!arrival[v]) { // not visited
                pass1(v);
            }
        }
        sequence.push(u);
    }
    const pass2 = (u, scc) => {  // run dfs on transpose graph
        arrival[u] = ++timer;
        scc.push(u);
        for (const v of transpose[u]) {
            if (!arrival[v]) { // unvisited
                pass2(v, scc);
            }
        }
    }
    // Pass 1: Get the sequence on original graph
    for (let i = 0; i < n; i++) {
        if (!arrival[i]) { // not visited
            pass1(i);
        }
    }
    // Pass 2: Find SCC running on transpose graph as per sequence
    arrival.fill(0);
    for (let i = n - 1; i >= 0; i--) {
        const u = sequence[i];
        if (!arrival[u]) {
            const scc = [];
            pass2(u, scc); // Every time we launch dfs, we detect a SCC
            // Update global ans
            if (scc.length > 1) {
                ans = Math.max(ans, scc.length);
            }
        }
    }
    return ans === 0 ? -1 : ans;
};

This post is based on Competitive Programming 4 — book 1. This book is amazing, feel free to buy this.

Happy coding :-)