DEV Community

Dev Cookies
Dev Cookies

Posted on

🔗 Blog 8: Strongly Connected Components (SCCs) & Bridges / Articulation Points

Graphs aren’t just about paths and trees — sometimes you need to understand the structure of connectivity itself. That’s where SCCs and critical edges/nodes come into play.

These concepts help in problems like:

  • Finding strongly connected “subsystems” in a directed graph.
  • Identifying critical links in a network (where removing one breaks connectivity).
  • Optimizing network design and fault-tolerance.

🌐 Part 1: Strongly Connected Components (SCCs)

🔎 What are SCCs?

  • In a directed graph, an SCC is a set of nodes where every node is reachable from every other node.
  • Example: In a social network, an SCC could represent a tight group of friends where everyone can reach everyone else.

📌 Why Important?

  • Break down directed graphs into condensed DAGs.
  • Basis for advanced problems like 2-SAT, deadlock detection, compiler optimization.

⚙️ Algorithms for SCCs

1. Kosaraju’s Algorithm (Two DFS Passes)

Steps:

  1. Do a DFS and store nodes in finish-time stack.
  2. Reverse the graph.
  3. Pop nodes from stack, run DFS in reversed graph → each DFS = one SCC.
class KosarajuSCC {
    private int V;
    private List<Integer>[] graph, revGraph;
    private boolean[] visited;
    private Stack<Integer> stack;

    KosarajuSCC(int V) {
        this.V = V;
        graph = new ArrayList[V];
        revGraph = new ArrayList[V];
        for (int i = 0; i < V; i++) {
            graph[i] = new ArrayList<>();
            revGraph[i] = new ArrayList<>();
        }
        visited = new boolean[V];
        stack = new Stack<>();
    }

    void addEdge(int u, int v) {
        graph[u].add(v);
        revGraph[v].add(u); // reverse edge
    }

    void dfs1(int u) {
        visited[u] = true;
        for (int v : graph[u]) {
            if (!visited[v]) dfs1(v);
        }
        stack.push(u);
    }

    void dfs2(int u, List<Integer> comp) {
        visited[u] = true;
        comp.add(u);
        for (int v : revGraph[u]) {
            if (!visited[v]) dfs2(v, comp);
        }
    }

    List<List<Integer>> getSCCs() {
        // Step 1: Order by finish time
        for (int i = 0; i < V; i++) {
            if (!visited[i]) dfs1(i);
        }

        // Step 2: Process in reverse graph
        Arrays.fill(visited, false);
        List<List<Integer>> sccs = new ArrayList<>();

        while (!stack.isEmpty()) {
            int u = stack.pop();
            if (!visited[u]) {
                List<Integer> comp = new ArrayList<>();
                dfs2(u, comp);
                sccs.add(comp);
            }
        }
        return sccs;
    }
}
Enter fullscreen mode Exit fullscreen mode

2. Tarjan’s Algorithm (Single DFS, O(V+E))

  • Uses low-link values to identify SCCs directly in one DFS.
  • More efficient in practice than Kosaraju.
class TarjanSCC {
    private List<Integer>[] graph;
    private int[] ids, low;
    private boolean[] onStack;
    private Stack<Integer> stack;
    private int id, sccCount;

    TarjanSCC(int n) {
        graph = new ArrayList[n];
        for (int i = 0; i < n; i++) graph[i] = new ArrayList<>();
        ids = new int[n];
        low = new int[n];
        Arrays.fill(ids, -1);
        onStack = new boolean[n];
        stack = new Stack<>();
        id = 0;
        sccCount = 0;
    }

    void addEdge(int u, int v) { graph[u].add(v); }

    void dfs(int at) {
        stack.push(at);
        onStack[at] = true;
        ids[at] = low[at] = id++;

        for (int to : graph[at]) {
            if (ids[to] == -1) dfs(to);
            if (onStack[to]) low[at] = Math.min(low[at], low[to]);
        }

        // Start of SCC
        if (ids[at] == low[at]) {
            while (true) {
                int node = stack.pop();
                onStack[node] = false;
                low[node] = ids[at];
                if (node == at) break;
            }
            sccCount++;
        }
    }

    int findSCCs() {
        for (int i = 0; i < graph.length; i++) {
            if (ids[i] == -1) dfs(i);
        }
        return sccCount;
    }
}
Enter fullscreen mode Exit fullscreen mode

🌉 Part 2: Bridges & Articulation Points

🔎 What are they?

  • Bridge (critical edge): Removing it increases number of connected components.
  • Articulation Point (cut vertex): Removing it disconnects the graph.

These help analyze network vulnerability.


⚙️ Tarjan’s Algorithm for Bridges

class Bridges {
    private List<Integer>[] graph;
    private int[] ids, low;
    private int id;
    private List<int[]> bridges;

    Bridges(int n) {
        graph = new ArrayList[n];
        for (int i = 0; i < n; i++) graph[i] = new ArrayList<>();
        ids = new int[n];
        low = new int[n];
        Arrays.fill(ids, -1);
        id = 0;
        bridges = new ArrayList<>();
    }

    void addEdge(int u, int v) {
        graph[u].add(v);
        graph[v].add(u);
    }

    void dfs(int at, int parent) {
        ids[at] = low[at] = id++;
        for (int to : graph[at]) {
            if (to == parent) continue;
            if (ids[to] == -1) {
                dfs(to, at);
                low[at] = Math.min(low[at], low[to]);
                if (ids[at] < low[to]) bridges.add(new int[]{at, to});
            } else {
                low[at] = Math.min(low[at], ids[to]);
            }
        }
    }

    List<int[]> findBridges() {
        for (int i = 0; i < graph.length; i++) {
            if (ids[i] == -1) dfs(i, -1);
        }
        return bridges;
    }
}
Enter fullscreen mode Exit fullscreen mode

⚙️ Tarjan’s Algorithm for Articulation Points

class ArticulationPoints {
    private List<Integer>[] graph;
    private int[] ids, low;
    private boolean[] visited, isArticulation;
    private int id, rootChildren, root;

    ArticulationPoints(int n) {
        graph = new ArrayList[n];
        for (int i = 0; i < n; i++) graph[i] = new ArrayList<>();
        ids = new int[n];
        low = new int[n];
        visited = new boolean[n];
        isArticulation = new boolean[n];
        id = 0;
    }

    void addEdge(int u, int v) {
        graph[u].add(v);
        graph[v].add(u);
    }

    void dfs(int at, int parent) {
        if (parent == root) rootChildren++;
        visited[at] = true;
        ids[at] = low[at] = id++;

        for (int to : graph[at]) {
            if (to == parent) continue;
            if (!visited[to]) {
                dfs(to, at);
                low[at] = Math.min(low[at], low[to]);
                if (ids[at] <= low[to]) isArticulation[at] = true;
            } else {
                low[at] = Math.min(low[at], ids[to]);
            }
        }
    }

    List<Integer> findAPs() {
        for (int i = 0; i < graph.length; i++) {
            if (!visited[i]) {
                root = i;
                rootChildren = 0;
                dfs(i, -1);
                isArticulation[i] = (rootChildren > 1);
            }
        }
        List<Integer> res = new ArrayList<>();
        for (int i = 0; i < graph.length; i++) if (isArticulation[i]) res.add(i);
        return res;
    }
}
Enter fullscreen mode Exit fullscreen mode

🚀 Time Complexity

  • SCC (Tarjan/Kosaraju): O(V + E)
  • Bridges & Articulation Points: O(V + E)

📝 Key Takeaways

  • SCCs: break directed graphs into strongly connected chunks.
  • Bridges & APs: identify critical edges/nodes for connectivity.
  • Tarjan’s algorithm (DFS + low-link values) unifies SCCs, bridges, and articulation points into a single powerful framework.

Top comments (0)