SCC.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 int[] ids;
    static int[] lowlink;
    static int[] result;
    static boolean[] instack;
    static Stack<Integer> stack;
    static int id;
    static int comp;
    
    public static void main(String[] args) {
        int n = 7;
        Graph graph = new Graph(n);
        graph.addAll(new int[][] {
            {0, 1},
            {1, 2},
            {2, 0},
            {1, 3},
            {3, 5},
            {5, 4},
            {4, 3},
            {3, 6},
            {6, 6}
        });
        ids = new int[n];
        instack = new boolean[n];
        lowlink = new int[n];
        result = new int[n];
        stack = new Stack<>();
        id = 0;
        comp = 1;
        for (int node = 0; node < n; node++) {
            if (ids[node] == 0) dfs(graph, 1);
        }
        System.out.println(Arrays.toString(result));
    }
    
    public static void dfs(Graph graph, int v) {
        ids[v] = lowlink[v] = ++id;
        stack.push(v);
        instack[v] = true;
        for (int w: graph.getNeiNodes(v)) {
            if (ids[w] == 0) {
                dfs(graph, w);
            }
        }
        for (int w: graph.getNeiNodes(v)) {
            if (instack[w]) {
                lowlink[v] = Math.min(lowlink[v], lowlink[w]); 
            }
        }
        
        if (ids[v] == lowlink[v]) {
            int x = -1;
            do {
                x = stack.pop();
                instack[x] = false;
                result[x] = comp;
            } while(x != v);
            comp++;
        }
    }
    
    
}

// output:

// [3, 3, 3, 2, 2, 2, 1]