From 664a4e9667c5cc25b0ea1344b74cb0cbd6f33707 Mon Sep 17 00:00:00 2001
From: Haidong Ji
Date: Sat, 23 May 2020 21:54:17 -0500
Subject: Topological sort not done yet. The program is correct but not
 efficient. I may need to convert the recursive DFS to iterative DFS. Check in
 now so I can get the code from the computer upstairs.

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

(limited to 'src/main')

diff --git a/src/main/Toposort.java b/src/main/Toposort.java
new file mode 100644
index 0000000..ede04b4
--- /dev/null
+++ b/src/main/Toposort.java
@@ -0,0 +1,64 @@
+import java.util.ArrayList;
+import java.util.Collections;
+import java.util.Scanner;
+
+public class Toposort {
+    private static ArrayList<Integer> toposort(ArrayList<ArrayList<Integer>> adj) {
+        int[] visited = new int[adj.size()];
+        ArrayList<Integer> postv = new ArrayList<>(Collections.nCopies(adj.size(),0));
+        int[] clock = new int[1];
+        dfs(adj, visited, postv, clock);
+
+        ArrayList<Integer> reverse_postv = (ArrayList<Integer>) postv.clone();
+        Collections.sort(reverse_postv, Collections.reverseOrder());
+
+        ArrayList<Integer> order = new ArrayList<Integer>();
+
+        for (int n : reverse_postv) {
+            order.add(postv.indexOf(n));
+        }
+
+        return order;
+    }
+
+    private static void dfs(ArrayList<ArrayList<Integer>> adj, int[] visited, ArrayList<Integer> postv, int[] clock) {
+        for (int v = 0; v < adj.size(); v++) {
+            if (visited[v] == 0)
+                explore(adj, v, visited, postv, clock);
+        }
+    }
+
+    private static void explore(ArrayList<ArrayList<Integer>> adj, int v, int[] visited, ArrayList<Integer> postv, int[] clock) {
+        visited[v] = 1;
+        clock[0] = clock[0] + 1;
+
+        for (int n : adj.get(v)) {
+            if (visited[n] == 0)
+                explore(adj, n, visited, postv, clock);
+        }
+        postv.set(v, clock[0]);
+        clock[0] = clock[0] + 1;
+
+    }
+
+    public static void main(String[] args) {
+        Scanner scanner = new Scanner(System.in);
+        int n = scanner.nextInt();
+        int m = scanner.nextInt();
+        ArrayList<ArrayList<Integer>> adj = new ArrayList<>();
+        for (int i = 0; i < n; i++) {
+            adj.add(new ArrayList<Integer>());
+        }
+        for (int i = 0; i < m; i++) {
+            int x, y;
+            x = scanner.nextInt();
+            y = scanner.nextInt();
+            adj.get(x - 1).add(y - 1);
+        }
+        ArrayList<Integer> order = toposort(adj);
+        for (int x : order) {
+            System.out.print((x + 1) + " ");
+        }
+    }
+}
+
-- 
cgit v1.2.3