summaryrefslogtreecommitdiff
path: root/sources
diff options
context:
space:
mode:
authorHaidong Ji2020-07-15 20:03:51 -0500
committerHaidong Ji2020-07-15 20:03:51 -0500
commit7e295af56cffda1dc0a65e3f905e58509dcafebc (patch)
tree1a3bac6185b35433f9df6a3d4a0630961a61abfa /sources
parent4347ebe961a2300782f880a5d63b6fce147dda28 (diff)
Strongly connected components done!
Diffstat (limited to 'sources')
-rw-r--r--sources/strongly_connected.py66
1 files changed, 66 insertions, 0 deletions
diff --git a/sources/strongly_connected.py b/sources/strongly_connected.py
new file mode 100644
index 0000000..c81725d
--- /dev/null
+++ b/sources/strongly_connected.py
@@ -0,0 +1,66 @@
+# Uses python3
+
+import sys
+
+sys.setrecursionlimit(200000)
+
+
+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 reverseG(adj):
+ adjReverse = [[] for _ in range(len(adj))]
+ for v in range(len(adj)):
+ for w in adj[v]:
+ adjReverse[w].append(v)
+
+ return adjReverse
+
+
+def dfs(adj, visited, postV, clock):
+ for v in range(len(adj)):
+ if visited[v] == False:
+ explore(v, adj, visited, postV, clock)
+
+
+def exploreWithoutPostV(v, adj, visited):
+ visited[v] = True
+ for w in adj[v]:
+ if visited[w] == False:
+ exploreWithoutPostV(w, adj, visited)
+
+
+def number_of_strongly_connected_components(adj):
+ adjReversal = reverseG(adj)
+ adjReversalVisited = [False] * len(adj)
+ postV = [0] * len(adj)
+ clock = [0]
+
+ dfs(adjReversal, adjReversalVisited, postV, clock)
+ temp = sorted(range(len(postV)), key=lambda k: postV[k], reverse=True)
+
+ visited = [False] * len(adj)
+ result = 0
+ for i in temp:
+ if visited[i] == False:
+ exploreWithoutPostV(i, adj, visited)
+ result = result + 1
+ return result
+
+
+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)
+ print(number_of_strongly_connected_components(adj))