Cod sursa(job #2927164)

Utilizator avethegamerAveTheGamer avethegamer Data 19 octombrie 2022 18:25:21
Problema Componente tare conexe Scor 0
Compilator py Status done
Runda Arhiva educationala Marime 1.26 kb
def citire_lista_adiacenta(fisier: str = "ctc.in"):
    with open(fisier) as f:
        nr_noduri, nr_muchii = [int(x) for x in f.readline().split()]
        lista = [[] for _ in range(nr_noduri + 1)]
        for _ in range(nr_muchii):
            linie = f.readline().split()
            x , y = int(linie[0]), int(linie[1])
            lista[x].append(y)
    return lista


lista = citire_lista_adiacenta()
vizitat = set([])
lista_componente_conexe = [[] for _ in range(len(lista))]
ordin = []


def dfs(nod):
    vizitat.add(nod)
    ordin.append(nod)
    for vecin in lista[nod]:
        if vecin not in vizitat:
            dfs(vecin)


def dfs_conex(nod):
    vizitat.add(nod)
    lista_componente_conexe[nr_componente_conexe].append(nod)
    for vecin in lista[nod]:
        if vecin not in vizitat:
            dfs_conex(vecin)


if __name__ == "__main__":
    nr_componente_conexe = 0
    for i in range(1, len(lista)):
        if i not in vizitat:
            dfs(i)
    vizitat.clear()
    for i in range(len(ordin) - 2, 0, -1):
        nod = ordin[i]
        if nod not in vizitat:
            nr_componente_conexe += 1
            dfs_conex(nod)
    print(nr_componente_conexe)
    for i in range(1, len(lista_componente_conexe)):
        print(*lista_componente_conexe[i])