StronglyConnected.java

// Advanced Problem: Checking Whether Any Intersection in a City is Reachable from Any Other
//Task. Compute the number of strongly connected components of a given directed graph with n vertices and m edges.
// Input Format. A graph is given in the standard format.
// Constraints. 1 ≤ n ≤ 10 4 , 0 ≤ m ≤ 10 4 .
// Output Format. Output the number of strongly connected components.
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Scanner;
import java.util.Stack;
import java.util.PriorityQueue;

public class StronglyConnected {
    static class VertexPost implements Comparable<VertexPost> {
        int postorder;
        int vertex;

        public VertexPost(int p, int v) {
            postorder = p;
            vertex = v;
        }

        public int compareTo(VertexPost v) {
            return v.postorder - this.postorder;
        }

        public String toString() {
            return vertex + "(" + postorder + ")";
        }
    }

    private static void dfs(ArrayList<Integer>[] adj, PriorityQueue<VertexPost> pq) {
        int order = 0;
        boolean[] visited = new boolean[adj.length];
        Stack<Integer> vStack = new Stack<>();
        Stack<Integer> postOrderStack = new Stack<>();
        for (int v = 0; v < adj.length; v++) {
            if (visited[v]) {
                continue;
            }
            // visited[v] = true;
            // order++;
            vStack.push(v);
            while (!vStack.isEmpty()) {
                int x = vStack.pop();
                if (visited[x]) {
                    continue;
                }
                order++;
                visited[x] = true;
                postOrderStack.push(x);
                for (int i = adj[x].size() - 1; i >= 0; i--) {
                    int u = adj[x].get(i);
                    vStack.push(u);
                }
            }
            while(!postOrderStack.isEmpty()) {
                int x = postOrderStack.pop();
                order++;
                if (pq != null) {
                    pq.add(new VertexPost(order, x));
                }
            }
        }
        // System.out.println(pq.toString());
    }

    private static int numberOfStronglyConnectedComponents(ArrayList<Integer>[] adj) {
        // write your code here
        ArrayList<Integer>[] reverse_adj = (ArrayList<Integer>[]) new ArrayList[adj.length];

        for (int v = 0; v < adj.length; v++) {
            if (reverse_adj[v] == null) {
                reverse_adj[v] = new ArrayList<>();
            }
            for (Integer u : adj[v]) {
                if (reverse_adj[u] == null) {
                    reverse_adj[u] = new ArrayList<>();
                }
                reverse_adj[u].add(v);
            }
        }

        // System.out.println(Arrays.toString(reverse_adj));

        PriorityQueue<VertexPost> pq = new PriorityQueue<>();
        
        dfs(reverse_adj, pq);

        int vertexNumberLeft = adj.length;
        Stack<Integer> vStack = new Stack<>();
        int[] cc = new int[adj.length];
        int countOfCC = 0;
        while (vertexNumberLeft > 0) {
            VertexPost largestPostOrderVertex = pq.poll();
            // System.out.println(largestPostOrderVertex);
            int v = largestPostOrderVertex.vertex;
            boolean[] visited = new boolean[adj.length];
            // if (visited[v]) {
            //     continue;
            // }
            if (cc[v] != 0) {
                continue;
            }
            // visited[v] = true;
            countOfCC++;
            cc[v] = countOfCC;
            vStack.push(v);
            while(!vStack.isEmpty()) {
                int x = vStack.pop();
                if (visited[x] || (cc[x] != cc[v] && cc[x] != 0)) {
                    continue;
                }
                visited[x] = true;
                vertexNumberLeft--;
                for (Integer u: adj[x]) {
                    vStack.push(u);
                }
            }
        }
        return countOfCC;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int m = scanner.nextInt();
        ArrayList<Integer>[] adj = (ArrayList<Integer>[]) new ArrayList[n];
        for (int i = 0; i < n; i++) {
            adj[i] = new ArrayList<Integer>();
        }
        for (int i = 0; i < m; i++) {
            int x, y;
            x = scanner.nextInt();
            y = scanner.nextInt();
            adj[x - 1].add(y - 1);
        }
        System.out.println(numberOfStronglyConnectedComponents(adj));
    }
}

Failed case #5/22: (Wrong answer)

Input:
100 100
27 96
23 51
42 10
40 22
30 41
80 40
13 70
21 94
88 35
38 86
53 83
71 84
64 26
4 46
76 43
24 76
26 83
18 75
42 98
36 39
47 63
33 96
89 54
47 80
95 8
34 41
91 45
78 1
12 74
2 37
98 81
30 32
93 30
45 71
38 44
85 18
89 10
71 35
73 52
28 42
98 20
22 69
56 79
78 63
53 58
77 13
6 11
56 36
4 11
92 63
32 78
71 24
16 79
66 89
72 6
20 15
2 91
100 75
93 7
42 100
18 88
49 75
33 78
81 1
42 95
73 64
50 66
33 68
14 38
80 89
8 16
87 18
20 80
81 38
14 35
91 20
36 5
16 8
61 11
72 91
26 57
60 83
80 11
58 1
71 36
41 30
57 46
47 82
46 74
28 9
76 70
69 58
39 73
89 55
93 54
17 92
54 44
21 69
87 58
96 34

Your output:
97

Correct output:
98
(Time used: 0.49/1.50, memory used: 26714112/536870912.)