From 7e295af56cffda1dc0a65e3f905e58509dcafebc Mon Sep 17 00:00:00 2001 From: Haidong Ji Date: Wed, 15 Jul 2020 20:03:51 -0500 Subject: Strongly connected components done! --- sources/strongly_connected.py | 66 +++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 66 insertions(+) create mode 100644 sources/strongly_connected.py (limited to 'sources') 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)) -- cgit v1.2.3