From daaaba9cd6dcaa885c18b7597e2cdc19c2be9726 Mon Sep 17 00:00:00 2001
From: Haidong Ji
Date: Tue, 14 Jul 2020 21:51:58 -0500
Subject: Strongly Connected Component done. It's easy after I struggled with
 topological sorting.

---
 src/main/StronglyConnected.java | 87 +++++++++++++++++++++++++++++++++++++++++
 1 file changed, 87 insertions(+)
 create mode 100644 src/main/StronglyConnected.java

diff --git a/src/main/StronglyConnected.java b/src/main/StronglyConnected.java
new file mode 100644
index 0000000..adc045b
--- /dev/null
+++ b/src/main/StronglyConnected.java
@@ -0,0 +1,87 @@
+import java.util.ArrayList;
+import java.util.Collections;
+import java.util.Scanner;
+import java.util.stream.IntStream;
+
+public class StronglyConnected {
+    private static int numberOfStronglyConnectedComponents(ArrayList<Integer>[] adj) {
+        ArrayList<Integer>[] adjReversa1 = reverseG(adj);
+        boolean[] adjReversalVisited = new boolean[adj.length];
+        int[] postV = new int[adj.length];
+        int[] clock = new int[1];
+        dfs(adjReversa1, adjReversalVisited, postV, clock);
+
+        // https://stackoverflow.com/questions/951848/java-array-sort-quick-way-to-get-a-sorted-list-of-indices-of-an-array/35701049
+        int[] temp = IntStream.range(0, postV.length).boxed().sorted((i, j) -> postV[i] - postV[j]).mapToInt(ele -> ele).toArray();
+
+        boolean[] visited = new boolean[adj.length];
+        int sccCount = 0;
+
+
+        for (int i = adj.length - 1; i > -1; i--) {
+            if (!visited[temp[i]]) {
+                exploreWithoutPostV(temp[i], adj, visited);
+                sccCount++;
+            }
+        }
+        return sccCount;
+    }
+
+    private static void dfs(ArrayList<Integer>[] adj, boolean[] visited, int[] postV, int[] clock) {
+        for (int v = 0; v < adj.length; v++) {
+            if (!visited[v])
+                explore(v, adj, visited, postV, clock);
+        }
+    }
+
+    private static void explore(int v, ArrayList<Integer>[] adj, boolean[] visited, int[] postV, int[] clock) {
+        visited[v] = true;
+        for (int w : adj[v]) {
+            if (!visited[w])
+                explore(w, adj, visited, postV, clock);
+        }
+        postV[v] = clock[0];
+        clock[0] = clock[0] + 1;
+    }
+
+    private static void exploreWithoutPostV(int v, ArrayList<Integer>[] adj, boolean[] visited) {
+        visited[v] = true;
+        for (int w : adj[v]) {
+            if (!visited[w])
+                exploreWithoutPostV(w, adj, visited );
+        }
+    }
+
+
+    private static ArrayList<Integer>[] reverseG(ArrayList<Integer>[] adj) {
+        ArrayList<Integer>[] adjReverse = (ArrayList<Integer>[])new ArrayList[adj.length];
+        for (int i = 0; i < adj.length; i++) {
+            adjReverse[i] = new ArrayList<Integer>();
+        }
+
+        for (int v = 0; v < adj.length; v++) {
+            for (int w : adj[v]) {
+                adjReverse[w].add(v);
+            }
+        }
+        return adjReverse;
+    }
+
+    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));
+    }
+}
+
-- 
cgit v1.2.3