Cod sursa(job #2937297)

Utilizator mbrianaMerealbe Cris-Briana mbriana Data 10 noiembrie 2022 10:19:02
Problema Componente tare conexe Scor 0
Compilator py Status done
Runda Arhiva educationala Marime 1.66 kb
# MEREALBE BRIANA, 243
# COMPONENTE TARE CONEXE
import sys

f = open("ctc.in")
linie = f.readline()
linie = linie.split()
n = int(linie[0])  # nr noduri
m = int(linie[1])  # nr muchii
lista_muchii = []
for i in range(0, m):
    linie = f.readline()
    linie = linie.split()
    p = []
    for j in linie:
        p.append(int(j))
    lista_muchii.append(p)


def DFS(nod: int, lista_adiacenta: list[list[int]], vizitate: list[int], stack: list[int]) -> None:
    vizitate[nod] = 1
    for n in lista_adiacenta[nod]:
        if not vizitate[n]:
            DFS(n, lista_adiacenta, vizitate, stack)
    stack.append(nod)

#algoritmul lui Kosaraju:

def ctc(n: int, lista_muchii: list[list[int]]) -> list[list[int]]:

    vizitate1 = [0 for i in range(n + 1)]
    lista_adiacenta = [[] for i in range(n + 1)]
    lista_adiacenta_inversata = [[] for i in range(n + 1)]

    for muchie in lista_muchii:
        lista_adiacenta[muchie[0]].append(muchie[1])
        lista_adiacenta_inversata[muchie[1]].append(muchie[0])

    stack = []

    for nod in range(1, n + 1):
        if not vizitate1[nod]:
            DFS(nod, lista_adiacenta, vizitate1, stack)

    vizitate2 = [0 for i in range(n + 1)]
    rezultat = []
    while len(stack) > 0:
        nod = stack.pop()
        if not vizitate2[nod]:
            componenta = []
            DFS(nod, lista_adiacenta_inversata, vizitate2, componenta)
            rezultat.append(componenta)

    return rezultat

solutie = ctc(n,lista_muchii)
with open('ctc.out', 'w') as f:
    print(len(solutie), file=f)
    for i in range(len(solutie)):
        solutie[i].sort()
        print(*solutie[i], file=f)