From ce12bcff9ee1185fc7180eac5b52cdb9fa8ad5ff Mon Sep 17 00:00:00 2001
From: Haidong Ji
Date: Mon, 13 Jul 2020 21:14:45 -0500
Subject: Topological sort done, easy after Java version is complete.

---
 Sources/GraphAlgo.cpp | 109 ++++++++++++++++++++++++++++++--------------------
 1 file changed, 65 insertions(+), 44 deletions(-)

(limited to 'Sources')

diff --git a/Sources/GraphAlgo.cpp b/Sources/GraphAlgo.cpp
index 3fdd795..3da7c8d 100644
--- a/Sources/GraphAlgo.cpp
+++ b/Sources/GraphAlgo.cpp
@@ -4,62 +4,83 @@
 #include <vector>
 #include <algorithm>
 
+
+#include <iostream>
+#include <algorithm>
+#include <vector>
+#include <numeric>
+
 using std::vector;
-//using std::pair;
+using std::pair;
+using namespace std;
+
+// https://stackoverflow.com/questions/1577475/c-sorting-and-keeping-track-of-indexes
+template <typename T>
+vector<size_t> sort_indexes(const vector<T>& v) {
 
-void explore(vector<vector<int>> &adj, int v, vector<int> &visited, vector<int> &prev,
-		vector<int> &postv, vector<int> &clock) {
-	visited.push_back(v);
-	prev[v] = clock[0];
-	clock[0] = clock[0] + 1;
+    // initialize original index locations
+    vector<size_t> idx(v.size());
+    iota(idx.begin(), idx.end(), 0);
 
-	for (size_t i = 0; i < adj[v].size(); i++) {
-		if (std::find(visited.begin(), visited.end(), adj[v][i])
-				== visited.end())
-			explore(adj, adj[v][i], visited, prev, postv, clock);
-	}
-	postv[v] = clock[0];
-	clock[0] = clock[0] + 1;
+    // sort indexes based on comparing values in v
+    // using std::stable_sort instead of std::sort
+    // to avoid unnecessary index re-orderings
+    // when v contains elements of equal values
+    stable_sort(idx.begin(), idx.end(),
+        [&v](size_t i1, size_t i2) {return v[i1] > v[i2]; });
 
+    return idx;
 }
 
-void dfs(vector<vector<int>> &adj, vector<int> &visited, vector<int> &prev,
-		vector<int> &postv, vector<int> &clock) {
-	for (size_t v = 0; v < adj.size(); v++) {
-		if (std::find(visited.begin(), visited.end(), v) == visited.end())
-			explore(adj, v, visited, prev, postv, clock);
-	}
+void postVisit(int v, vector<int>& clock, vector<int>& postV) {
+    postV[v] = clock[0];
+    clock[0] = clock[0] + 1;
+}
+void explore(int v, vector<vector<int>> &adj, vector<bool>& visited, vector<int>& postV, vector<int>& clock) {
+    visited[v] = true;
+    for (int w : adj[v]) {
+        if (!visited[w])
+            explore(w, adj, visited, postV, clock);
+    }
+    postVisit(v, clock, postV);
 }
 
-int acyclic(vector<vector<int> > &adj) {
-	vector<int> visited;
-	vector<int> prev(adj.size(), 0);
-	vector<int> postv(adj.size(), 0);
-	vector<int> clock(1, 0);
-	dfs(adj, visited, prev, postv, clock);
+void dfs(vector<vector<int> >& adj, vector<bool>& visited, vector<int>& postV, vector<int>& clock) {
+    for (size_t v = 0; v < adj.size(); v++) {
+        if (!visited[v])
+            explore(v, adj, visited, postV, clock);
+    }
+}
 
-	for (size_t u = 0; u < adj.size(); u++) {
-		for (size_t i = 0; i < adj[u].size(); i++) {
-			if (postv[u] <= postv[adj[u][i]])
-				return 1;
-		}
-	}
-	return 0;
+vector<int> toposort(vector<vector<int> > adj) {
+    vector<bool> visited(adj.size(), false);
+    vector<int> order;
+    vector<int> postV(adj.size(), 0);
+    vector<int> clock(1, 0);
+
+    dfs(adj, visited, postV, clock);
+    for (auto i : sort_indexes(postV)) {
+        order.push_back(i);
+    }
+    return order;
+}
+
+int main() {
+    size_t n, m;
+    std::cin >> n >> m;
+    vector<vector<int> > adj(n, vector<int>());
+    for (size_t i = 0; i < m; i++) {
+        int x, y;
+        std::cin >> x >> y;
+        adj[x - 1].push_back(y - 1);
+    }
+    vector<int> order = toposort(adj);
+    for (size_t i = 0; i < order.size(); i++) {
+        std::cout << order[i] + 1 << " ";
+    }
 }
 
 //TEST(Acyclicity, ac1) {
 //	vector<vector<int>> adj = { { 1 }, { 2 }, { 0 }, { 0 } };
 //	ASSERT_EQ(acyclic(adj), 1);
 //}
-
-int main() {
-  size_t n, m;
-  std::cin >> n >> m;
-  vector<vector<int> > adj(n, vector<int>());
-  for (size_t i = 0; i < m; i++) {
-    int x, y;
-    std::cin >> x >> y;
-    adj[x - 1].push_back(y - 1);
-  }
-  std::cout << acyclic(adj);
-}
-- 
cgit v1.2.3