ReversedTopSort.java

// https://www.cs.cmu.edu/~15451-f18/lectures/lec19-DFS-strong-components.pdf

import java.util.*;

class Graph {
    
    ArrayList<Integer>[] graph;
    
    public Graph(int n) {
        graph = new ArrayList[n];
        for (int i = 0; i< n ;i ++) {
            graph[i] = new ArrayList<Integer>();
        }
    }
    
    public void addEdge(int i, int j) {
        graph[i].add(j);
    }
    
    public ArrayList<Integer> getNeiNodes(int node) {
        return graph[node];
    }
    
    public void addAll(int[][] edges) {
        for (int[] edge: edges) {
            addEdge(edge[0], edge[1]);
        }
    }
    
}


class SCC {
    
    static boolean[] visited;
    static ArrayList<Integer> result;
    
    public static void main(String[] args) {
        int n = 13;
        Graph graph = new Graph(n);
        graph.addAll(new int[][] {
            {0, 1},
            {0, 2},
            {1, 3},
            {1, 4},
            {3, 7},
            {3, 8},
            {4, 9},
            {4, 10},
            {0, 4},
            {2, 5},
            {2, 6},
            {5, 11},
            {5, 12}
        });
        visited = new boolean[n];
        result = new ArrayList<>();
        for (int node = 0; node < n; node++) {
            if (!visited[node]) topSort(graph, 0);
        }
        System.out.println(result);
    }
    
    public static void topSort(Graph graph, int node) {
        if(visited[node]) {
           return; 
        }
        visited[node] = true;
        for (int n: graph.getNeiNodes(node)) {
            topSort(graph, n);
        }
        result.add(node);
    }
    
    
}