Cod sursa(job #2924706)

Utilizator DariaClemClem Daria DariaClem Data 9 octombrie 2022 01:29:37
Problema Componente tare conexe Scor 0
Compilator py Status done
Runda Arhiva educationala Marime 1.28 kb
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")