Advanced Graph Algorithms

Strongly Connected Components

What are Strongly Connected Components?

A Strongly Connected Component (SCC) is a maximal set of vertices such that there is a path from each vertex to every other vertex in the set.

Kosaraju's Algorithm

Two-pass DFS approach:

Perform DFS on original graph, push nodes to stack in finish order
Reverse the graph
Pop nodes from stack, perform DFS on reversed graph

public class KosarajuSCC {
    private List<List<Integer>> adj;
    private List<List<Integer>> revAdj;
    private boolean[] visited;
    private Stack<Integer> stack;
    private int n;
    
    public List<List<Integer>> findSCCs(int n, int[][] edges) {
        this.n = n;
        adj = new ArrayList<>();
        revAdj = new ArrayList<>();
        
        for (int i = 0; i < n; i++) {
            adj.add(new ArrayList<>());
            revAdj.add(new ArrayList<>());
        }
        
        for (int[] edge : edges) {
            adj.get(edge[0]).add(edge[1]);
            revAdj.get(edge[1]).add(edge[0]);
        }
        
        // Step 1: Fill stack with finish times
        visited = new boolean[n];
        stack = new Stack<>();
        for (int i = 0; i < n; i++) {
            if (!visited[i]) {
                dfs1(i);
            }
        }
        
        // Step 2: Process reversed graph
        visited = new boolean[n];
        List<List<Integer>> sccs = new ArrayList<>();
        
        while (!stack.isEmpty()) {
            int node = stack.pop();
            if (!visited[node]) {
                List<Integer> scc = new ArrayList<>();
                dfs2(node, scc);
                sccs.add(scc);
            }
        }
        
        return sccs;
    }
    
    private void dfs1(int node) {
        visited[node] = true;
        for (int next : adj.get(node)) {
            if (!visited[next]) {
                dfs1(next);
            }
        }
        stack.push(node);
    }
    
    private void dfs2(int node, List<Integer> scc) {
        visited[node] = true;
        scc.add(node);
        for (int next : revAdj.get(node)) {
            if (!visited[next]) {
                dfs2(next, scc);
            }
        }
    }
}

Tarjan's Algorithm (Single Pass)

public class TarjanSCC {
    private List<List<Integer>> adj;
    private int[] disc, low;
    private boolean[] inStack;
    private Stack<Integer> stack;
    private int time;
    private List<List<Integer>> sccs;
    
    public List<List<Integer>> findSCCs(int n, int[][] edges) {
        adj = new ArrayList<>();
        for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
        for (int[] e : edges) adj.get(e[0]).add(e[1]);
        
        disc = new int[n];
        low = new int[n];
        inStack = new boolean[n];
        stack = new Stack<>();
        sccs = new ArrayList<>();
        Arrays.fill(disc, -1);
        
        for (int i = 0; i < n; i++) {
            if (disc[i] == -1) {
                dfs(i);
            }
        }
        
        return sccs;
    }
    
    private void dfs(int u) {
        disc[u] = low[u] = time++;
        stack.push(u);
        inStack[u] = true;
        
        for (int v : adj.get(u)) {
            if (disc[v] == -1) {
                dfs(v);
                low[u] = Math.min(low[u], low[v]);
            } else if (inStack[v]) {
                low[u] = Math.min(low[u], disc[v]);
            }
        }
        
        // If u is root of SCC
        if (low[u] == disc[u]) {
            List<Integer> scc = new ArrayList<>();
            while (true) {
                int v = stack.pop();
                inStack[v] = false;
                scc.add(v);
                if (v == u) break;
            }
            sccs.add(scc);
        }
    }
}

Time Complexity

Kosaraju's: O(V + E)
Tarjan's: O(V + E)

Bridges and Articulation Points

Bridges in Undirected Graph

A bridge is an edge whose removal increases the number of connected components.

public class FindBridges {
    private List<List<Integer>> adj;
    private int[] disc, low;
    private int time;
    private List<int[]> bridges;
    
    public List<int[]> findBridges(int n, int[][] edges) {
        adj = new ArrayList<>();
        for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
        for (int[] e : edges) {
            adj.get(e[0]).add(e[1]);
            adj.get(e[1]).add(e[0]);
        }
        
        disc = new int[n];
        low = new int[n];
        Arrays.fill(disc, -1);
        bridges = new ArrayList<>();
        
        dfs(0, -1);
        return bridges;
    }
    
    private void dfs(int u, int parent) {
        disc[u] = low[u] = time++;
        
        for (int v : adj.get(u)) {
            if (v == parent) continue;
            
            if (disc[v] == -1) {
                dfs(v, u);
                low[u] = Math.min(low[u], low[v]);
                
                // Bridge found!
                if (low[v] > disc[u]) {
                    bridges.add(new int[]{u, v});
                }
            } else {
                low[u] = Math.min(low[u], disc[v]);
            }
        }
    }
}

Articulation Points

An articulation point is a vertex whose removal increases the number of connected components.

public class FindArticulationPoints {
    private List<List<Integer>> adj;
    private int[] disc, low;
    private boolean[] visited;
    private int time;
    private Set<Integer> articulationPoints;
    
    public List<Integer> findArticulationPoints(int n, int[][] edges) {
        adj = new ArrayList<>();
        for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
        for (int[] e : edges) {
            adj.get(e[0]).add(e[1]);
            adj.get(e[1]).add(e[0]);
        }
        
        disc = new int[n];
        low = new int[n];
        visited = new boolean[n];
        articulationPoints = new HashSet<>();
        
        for (int i = 0; i < n; i++) {
            if (!visited[i]) {
                dfs(i, -1, 0);
            }
        }
        
        return new ArrayList<>(articulationPoints);
    }
    
    private void dfs(int u, int parent, int children) {
        visited[u] = true;
        disc[u] = low[u] = time++;
        int childCount = 0;
        
        for (int v : adj.get(u)) {
            if (!visited[v]) {
                childCount++;
                dfs(v, u, childCount);
                low[u] = Math.min(low[u], low[v]);
                
                // Root with 2+ children is articulation point
                if (parent == -1 && childCount > 1) {
                    articulationPoints.add(u);
                }
                
                // Non-root: if low[v] >= disc[u], u is articulation point
                if (parent != -1 && low[v] >= disc[u]) {
                    articulationPoints.add(u);
                }
            } else if (v != parent) {
                low[u] = Math.min(low[u], disc[v]);
            }
        }
    }
}

Applications

Network reliability: Find critical edges/nodes
Road networks: Identify vulnerable connections
Social networks: Find influential users

Practice Problems

0/1solved

hardCritical Connections in a Network

Tarjan's Bridge Finding

There are n servers labeled from 0 to n-1 connected by undirected connections. A critical connection is an connection that, if removed, will make some servers unable to reach some other server. Return all critical connections.

Example:

Input: n = 4, connections = [[0,1],[1,2],[2,0],[1,3]]

Output: 13

Connection [1,3] is critical. Removing it disconnects server 3.

Solution

```java
public List<List<Integer>> criticalConnections(int n, List<List<Integer>> connections) {
    List<List<Integer>> adj = new ArrayList<>();
    for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
    for (List<Integer> conn : connections) {
        adj.get(conn.get(0)).add(conn.get(1));
        adj.get(conn.get(1)).add(conn.get(0));
    }
    
    int[] disc = new int[n];
    int[] low = new int[n];
    Arrays.fill(disc, -1);
    List<List<Integer>> bridges = new ArrayList<>();
    
    dfs(0, -1, disc, low, adj, bridges);
    return bridges;
}

private void dfs(int u, int parent, int[] disc, int[] low,
                 List<List<Integer>> adj, List<List<Integer>> bridges) {
    disc[u] = low[u] = time++;
    
    for (int v : adj.get(u)) {
        if (v == parent) continue;
        
        if (disc[v] == -1) {
            dfs(v, u, disc, low, adj, bridges);
            low[u] = Math.min(low[u], low[v]);
            
            if (low[v] > disc[u]) {
                bridges.add(Arrays.asList(u, v));
            }
        } else {
            low[u] = Math.min(low[u], disc[v]);
        }
    }
}
```

Edge Cases:

Single connected component
Multiple disconnected components
Linear chain (all edges are bridges)
Complete graph (no bridges)

Flashcards

Question

What is the difference between Kosaraju's and Tarjan's SCC algorithms?

Click to reveal answer

Answer

Kosaraju's uses two passes (DFS on original + reversed graph) while Tarjan's finds SCCs in a single pass using discovery and low-link values. Both run in O(V+E) time.

Question

How do you detect a bridge in an undirected graph using DFS?

Click to reveal answer

Answer

Edge (u,v) is a bridge if low[v] > disc[u]. This means no back edge exists from v's subtree to u or its ancestors, so removing (u,v) disconnects the graph.

Question

What is Advanced Graph Algorithms?

Click to reveal answer

Answer

Advanced Graph Algorithms is a key concept in software engineering.

Question

When to use Advanced Graph Algorithms?

Click to reveal answer

Answer

Use Advanced Graph Algorithms when building production systems that require reliability, scalability, and maintainability.

Question

Advanced Graph Algorithms best practices

Click to reveal answer

Answer

Follow SOLID principles, write clean code, test thoroughly, document decisions, and monitor in production.

Revision Notes

Key Takeaways

1.SCCs partition directed graphs into maximal strongly connected subgraphs
2.Kosaraju's uses two DFS passes; Tarjan's uses one pass with low-link values
3.Bridges have no back edge: low[v] > disc[u]
4.Articulation points have no alternative path: low[v] >= disc[u]
5.All algorithms run in O(V+E) time

Interview Tips

•For SCC problems, know both Kosaraju's and Tarjan's approaches
•Bridge detection: if low[v] > disc[u], edge (u,v) is a bridge
•Articulation points: root needs 2+ children, others need low[v] >= disc[u]
•Graph condensation: compress SCCs to get a DAG
•Practice: Critical Connections, Strongly Connected Components, Articulation Point

Cheat Sheet