Strongly connected components

In a directed graph, a Strongly Connected Component (SCC) is a maximal group of vertices such that every vertex is reachable from every other vertex within the group.

we have 2 popular algorithms:

1. Kosaraju’s Algorithm
2. Tarjan’s Algorithm

Kosaraju’s Algorithm Steps:

1. Do DFS on original graph, and store vertices in stack by finishing time (postorder).
2. Reverse all edges (transpose graph).
3. Pop vertices from stack (from last finished to first), and run DFS on reversed graph.

• Each DFS call gives one SCC.

Time Complexity: O(V + E)
Space Complexity: O(V + E) (for reversed graph)

Tarjan’s Algorithm Steps:

Initialize

• disc[u] = -1 for all vertices (unvisited)
• low[u] = ∞, inStack[u] = false, stack = empty ,time = 0
• For each unvisited vertex u:
  Call tarjan(u)

Intarjan(u):

• Set disc[u] = low[u] = time++ push u into stack inStack[u] = true
• For every neighbor v of u:
• If v is unvisited, call tarjan(v) and then
  low[u] = min(low[u], low[v])
• Else if v is in stack,
  low[u] = min(low[u], disc[v])
• If low[u] == disc[u] → u is head of an SCC
• Pop nodes from the stack until you pop u
• All popped nodes form one SCC
• Repeat until all vertices are visited.

Find the bridges: edge (u → v) is a bridge if removing it increases the number of Strongly Connected Components (SCCs) in the graph.

Get Sanjayharivilaspal’s stories in your inbox

Join Medium for free to get updates from this writer.

Remember me for faster sign in

low[v]>dis[u] -> indicate the edge u-v is an bridge

Articulation Point: A vertex u is called an articulation point (or cut vertex) if removing u (and its edges) increases the number of connected components of the graph.

Case 1: Root of DFS Tree

If u is the root of the DFS tree
→ it is an articulation point if it has two or more children in the DFS tree.

if (parent[u] == -1 && childCount > 1)
    u is an articulation point

Case 2: Non-root Vertex

If u is not the root,
and there exists a child v such that:

low[v] >= disc[u]

then u is an articulation point.

Biconnected Component: A Biconnected Component (BCC) is a maximal subgraph in which removing any single vertex does NOT disconnect the subgraph.

No articulation point exists inside a BCC.

Articulation points act as boundaries between BCCs. so whenever we detect an articulation point condition (low[v] >= disc[u]).
We know that all edges from that subtree up to (u, v) form one BCC.

When you find a condition:

low[v] >= disc[u]

→ then (u, v) is the boundary of a BCC.
Pop all edges from the stack until (u, v) appears — these edges form one Biconnected Component.

Complete code to find bridge, Articulation point and BCC

package StronglyConnectedComponents;

import java.util.*;

public class TarjanAllInOne {
    static int time = 0;
    static Stack<int[]> edgeStack = new Stack<>();
    static Set<Integer> articulationPoints = new HashSet<>();
    static List<int[]> bridges = new ArrayList<>();
    static List<List<int[]>> biconnectedComponents = new ArrayList<>();
    static ArrayList<Set<Integer>> components= new ArrayList<>();
    public static void dfs(int u, int parent, int[] disc, int[] low, List<List<Integer>> graph, Set<Integer> component) {
        disc[u] = low[u] = ++time;
        int children = 0;
        component.add(u);
        for (int v : graph.get(u)) {
            if (v == parent) continue;

            if (disc[v] == -1) {
                children++;
                edgeStack.push(new int[]{u, v});
                dfs(v, u, disc, low, graph,component);
                low[u] = Math.min(low[u], low[v]);

                // Articulation point check
                if ((parent != -1 && low[v] >= disc[u]) || (parent == -1 && children > 1)) {
                    articulationPoints.add(u);
                }

                // Bridge check
                if (low[v] > disc[u]) {
                    bridges.add(new int[]{u, v});
                }

                // BCC check
                if (low[v] >= disc[u]) {
                    List<int[]> bcc = new ArrayList<>();
                    int[] edge;
                    do {
                        edge = edgeStack.pop();
                        bcc.add(edge);
                    } while (!(edge[0] == u && edge[1] == v));
                    biconnectedComponents.add(bcc);
                }
            } else if (disc[v] < disc[u]) {
                low[u] = Math.min(low[u], disc[v]);
                edgeStack.push(new int[]{u, v});
            }
        }
    }

    public static void findAll(int V, List<List<Integer>> graph) {
        int[] disc = new int[V];
        int[] low = new int[V];
        Arrays.fill(disc, -1);
        Arrays.fill(low, -1);

        for (int i = 0; i < V; i++) {
            Set<Integer> component= new HashSet<>();
            if (disc[i] == -1) {
                dfs(i, -1, disc, low, graph, component);
                components.add(component);
            }
        }
    }

    public static void main(String[] args) {
        int V = 5;
        List<List<Integer>> graph = new ArrayList<>();
        for (int i = 0; i < V; i++) graph.add(new ArrayList<>());

        graph.get(0).add(1); graph.get(1).add(0);
        graph.get(1).add(2); graph.get(2).add(1);
//        graph.get(2).add(0); graph.get(0).add(2);
//        graph.get(1).add(3); graph.get(3).add(1);
        graph.get(3).add(4); graph.get(4).add(3);

        findAll(V, graph);

        System.out.println("Articulation Points: " + articulationPoints);

        System.out.println("Bridges:");
        for (int[] bridge : bridges) {
            System.out.println(Arrays.toString(bridge));
        }

        System.out.println("Biconnected Components:");
        for (List<int[]> bcc : biconnectedComponents) {
            for (int[] edge : bcc) {
                System.out.print(Arrays.toString(edge) + " ");
            }
            System.out.println();
        }
        System.out.println(" Components:");
        for (Set<Integer> component: components) {
                System.out.println(component);
        }
    }
}