EdgeTypes.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[] mark;
    static boolean[] visited;
    static int id;
    
    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},
            {8, 0},
            {2, 5},
            {2, 6},
            {5, 11},
            {5, 12},
            {11, 2},
            {12, 3},
        });
        ids = new int[n];
        mark = new int[n];
        id = 0;
        for (int node = 0; node < n; node++) {
            if (ids[node] == 0) dfs(graph, 0);
        }
        for (int i = 0; i < n ; i++) {
            // System.out.printf("%d- %d \n", i, ids[i]);
        }
    }
    
    public static void dfs(Graph graph, int node) {
        ids[node] = ++id;
        mark[node] = 1;
        for (Integer n: graph.getNeiNodes(node)) {
            if (ids[n] == 0) {
                System.out.printf("%d-%d tree edge\n", node, n);
                dfs(graph, n);   
            } else if (ids[n] > ids[node]) {
                System.out.printf("%d-%d forward edge\n", node, n);
            } else if (mark[n] == 0) {
                System.out.printf("%d-%d cross edge\n", node, n);
            } else {
                System.out.printf("%d-%d back edge\n", node, n);
            }
        }
        mark[node] = 0;
    }
    
    
}


// output:

// 0-1 tree edge
// 1-3 tree edge
// 3-7 tree edge
// 3-8 tree edge
// 8-0 back edge
// 1-4 tree edge
// 4-9 tree edge
// 4-10 tree edge
// 0-2tree edge
// 2-5 tree edge
// 5-11 tree edge
// 11-2 back edge
// 5-12 tree edge
// 12-3 cross edge
// 2-6 tree edge
// 0-4 forward edge