Pagini recente » Cod sursa (job #1050184) | Cod sursa (job #2499828) | Cod sursa (job #2887001) | Cod sursa (job #2860989) | Cod sursa (job #2924706)
f = open("ctc.in", 'r')
g = open("ctc.out", 'w')
def dfs(curretNode, graph):
global visited, order
visited[curretNode] = 1
for nextNode in graph[curretNode]:
if visited[nextNode] == 0:
dfs(nextNode, graph)
order.append(curretNode)
fisier = f.read().split("\n")
nm = [int(x) for x in fisier[0].split()]
n, m = nm[0], nm[1]
initialGraph = {key: [] for key in range(1, n + 1)}
transposeGraph = {key: [] for key in range(1, n + 1)}
visited = [0] * (n + 1)
order = []
for i in range(m):
ab = [int(x) for x in fisier[i + 1].split()]
a, b = ab[0], ab[1]
if a in initialGraph:
initialGraph[a].append(b)
else:
initialGraph[a] = [b]
if b in transposeGraph:
transposeGraph[b].append(a)
else:
transposeGraph[b] = [a]
for node in initialGraph:
if visited[node] == 0:
dfs(node, initialGraph)
order = order[::-1]
visited = [0] * (n + 1)
result = []
counter = 0
for node in order:
if visited[node] == 0:
order = []
dfs(node, transposeGraph)
counter += 1
result.append(order)
print(result)
g.write(str(counter) + "\n")
for scc in result:
for number in scc[::-1]:
g.write(str(number) + " ")
g.write("\n")