summaryrefslogtreecommitdiff
path: root/sources
diff options
context:
space:
mode:
Diffstat (limited to 'sources')
-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=' ')