Java strongly connected components: mutual reachability with two traversals

Java 8+. The program uses JDK classes and requires no preview flags.

Direction changes the membership rule

A dependency graph can have one-way reachability without a cycle. Union-find on undirected endpoints would group that relation differently. Strong components need both directions of reachability, so this algorithm first records a finishing order and then walks the reversed graph.

The first pass below uses explicit DFS frames represented by each vertex’s next edge index. Marking a vertex when it is pushed prevents repeated pending entries from being mistaken for separate visits. A vertex enters the finishing list only after its outgoing edges have been considered.

The reversed pass visits vertices in reverse finishing order and assigns one component number per reached group. The numbers are traversal labels, not stable business identifiers. Reordering adjacency lists can change their numeric values while preserving the same component partition.

Validate every endpoint

Validate the whole graph before computing the partition. An invalid edge should not leave a half-built result that a caller mistakes for a complete grouping. The property tests compare component equality with an independent transitive-reachability matrix; they do not require one particular label numbering.

Working program

import java.util.*;
public class DependencyComponents {
    static int[] groups(int[][] edges){
        int n=edges.length;List<List<Integer>> reverse=new ArrayList<>();for(int i=0;i<n;i++)reverse.add(new ArrayList<>());
        for(int v=0;v<n;v++){if(edges[v]==null)throw new IllegalArgumentException("Missing adjacency");for(int next:edges[v]){if(next<0||next>=n)throw new IllegalArgumentException("Invalid endpoint");reverse.get(next).add(v);}}
        boolean[] seen=new boolean[n];int[] cursor=new int[n];List<Integer> finished=new ArrayList<>();ArrayDeque<Integer> stack=new ArrayDeque<>();
        for(int start=0;start<n;start++)if(!seen[start]){
            seen[start]=true;stack.push(start);
            while(!stack.isEmpty()){
                int v=stack.peek();if(cursor[v]<edges[v].length){int next=edges[v][cursor[v]++];if(!seen[next]){seen[next]=true;stack.push(next);}}
                else {stack.pop();finished.add(v);}
            }
        }
        int[] group=new int[n];Arrays.fill(group,-1);int label=0;
        for(int i=finished.size()-1;i>=0;i--){int start=finished.get(i);if(group[start]>=0)continue;group[start]=label;stack.push(start);
            while(!stack.isEmpty()){int v=stack.pop();for(int next:reverse.get(v))if(group[next]<0){group[next]=label;stack.push(next);}}
            label++;
        }return group;
    }
    public static void main(String[] args){
        int[] group=groups(new int[][]{{1},{0,2},{3},{2},{}});
        System.out.println(group[0]==group[1]);System.out.println(group[2]==group[3]);System.out.println(group[1]==group[2]);
    }
}

Output

true
true
false

Costs and boundaries

Both passes take O(V+E). The reversed adjacency storage uses O(V+E); traversal state uses O(V). Explicit stacks avoid recursion depth proportional to the graph path, but they do not remove the memory needed for a large graph.

Common Mistakes

• Undirected connectivity is not strong connectivity.
• Numeric component labels are not stable external IDs.
• Finishing order differs from discovery order.

Read next

Depth-first traversal, Dependency ordering.