Cod sursa(job #2924842)

Utilizator Valentin06Maftei Valentin Valentin06 Data 11 octombrie 2022 20:51:43
Problema Componente tare conexe Scor 0
Compilator py Status done
Runda Arhiva educationala Marime 1.44 kb
f = open("date.in", 'r')
fisier = f.readlines()

adiacenta = {}
adiacentaTranspusa = {}

nrNoduri = int(fisier[0].split()[0])
nrMuchii = int(fisier[0].split()[1])
nrComponente = 0

for i in range(1, nrNoduri + 1):
    adiacenta[i] = []
    adiacentaTranspusa[i] = []

i = 1
while i <= nrMuchii:
    adiacenta[int(fisier[i].split()[0])].append(int(fisier[i].split()[1]))
    adiacentaTranspusa[int(fisier[i].split()[1])].append(int(fisier[i].split()[0]))
    i += 1

stiva = []


def dfs(vizitat, adiacenta, nod):
    vizitat[nod] = 0
    for vecin in adiacenta[nod]:
        if vizitat[vecin] == -1:
            dfs(vizitat, adiacenta, vecin)
    stiva.append(nod)


def dfst(vizitat, adiacentaTranspusa, nod):
    vizitat[nod] = 0
    raspuns.append(nod)
    for vecin in adiacentaTranspusa[nod]:
        if vizitat[vecin] == -1:
            dfst(vizitat, adiacentaTranspusa, vecin)

vizitat = [-1] * (nrNoduri + 1)
for i in range(1, nrNoduri + 1):
    if vizitat[i] == -1:
        dfs(vizitat, adiacenta, i)

listaComponente = []

vizitat = [-1] * (nrNoduri + 1)
for i in range(nrNoduri - 1, 1, -1):
    raspuns = []
    if vizitat[stiva[i]] == -1:
        nrComponente += 1
        dfst(vizitat, adiacentaTranspusa, stiva[i])
        listaComponente.append(raspuns)

g = open("date.out", 'w')
g.write(str(nrComponente))
g.write('\n')
for listaMica in listaComponente:
    g.write(str(listaMica))
    g.write('\n')