Cod sursa(job #2928006)

Utilizator VartonVarts Var Varton Data 21 octombrie 2022 23:36:17
Problema Componente tare conexe Scor 0
Compilator py Status done
Runda Arhiva educationala Marime 1.48 kb
from collections import defaultdict, deque

f = open('ctc.in')
n, m = [int(x) for x in f.readline().split()]
adjList = defaultdict(list)
i = 0
while i < m:
    n1, n2 = [int(x) for x in f.readline().split()]
    adjList[n1].append(n2)
    i += 1

f.close()
print(adjList)


index = 0
indexes = [0] * (n + 1)
lowlinks = [0] * (n + 1)
stackStatus = [False] * (n + 1)
stack = deque()
nrComponents = 0
connectedComponents = deque()

def DFS(node):
    global index
    global nrComponents
    indexes[node] = index
    lowlinks[node] = index
    stack.append(node)
    stackStatus[node] = True
    index += 1

    for vecin in adjList[node]:
        if indexes[vecin] == 0:
            DFS(vecin)
            lowlinks[node] = min(lowlinks[node], lowlinks[vecin])
        elif stackStatus[vecin]:
            lowlinks[node] = min(lowlinks[node], indexes[vecin])



    if lowlinks[node] == indexes[node]:
        currentComponent = deque()
        nrComponents += 1
        el = -1
        while node != el:
            el = stack.pop()
            currentComponent.append(el)
            stackStatus[el] = False
        connectedComponents.append(currentComponent)



DFS(list(adjList.keys())[0])

out = open('ctc.out', 'a')
out.write(str(nrComponents))
out.write("\n")
while connectedComponents:
    component = connectedComponents.pop()
    while component:
        out.write(str(component.pop()))
        out.write(' ')
    out.write("\n")

out.close()