summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorHaidong Ji2020-07-13 22:02:36 -0500
committerHaidong Ji2020-07-13 22:02:36 -0500
commit4347ebe961a2300782f880a5d63b6fce147dda28 (patch)
tree21fa98c9a6004e543f795823b5003f8b6da09a2b
parentb8349cfc102edc3964868c6ff3299e6537c36ae1 (diff)
Topological ordering done!
-rw-r--r--sources/topsort.py43
1 files changed, 43 insertions, 0 deletions
diff --git a/sources/topsort.py b/sources/topsort.py
new file mode 100644
index 0000000..37f4ba0
--- /dev/null
+++ b/sources/topsort.py
@@ -0,0 +1,43 @@
+# Uses python3
+
+import sys
+
+
+def explore(v, adj, visited, postV, clock):
+ visited[v] = True
+ for w in adj[v]:
+ if visited[w] == False:
+ explore(w, adj, visited, postV, clock)
+ postV[v] = clock[0]
+ clock[0] = clock[0] + 1
+
+
+def dfs(adj, visited, postV, clock):
+ for v in range(len(adj)):
+ if visited[v] == False:
+ explore(v, adj, visited, postV, clock)
+
+
+def toposort(adj):
+ visited = [False] * len(adj)
+ order = []
+ postV = [0] * len(adj)
+ clock = [0]
+
+ dfs(adj, visited, postV, clock)
+ order = sorted(range(len(postV)), key=lambda k: postV[k], reverse=True)
+ return order
+
+
+if __name__ == '__main__':
+ input = sys.stdin.read()
+ data = list(map(int, input.split()))
+ n, m = data[0:2]
+ data = data[2:]
+ edges = list(zip(data[0:(2 * m):2], data[1:(2 * m):2]))
+ adj = [[] for _ in range(n)]
+ for (a, b) in edges:
+ adj[a - 1].append(b - 1)
+ order = toposort(adj)
+ for x in order:
+ print(x + 1, end=' ')