Cod sursa(job #3372445)

Utilizator david18.6yDavid Popa david18.6y Data 3 noiembrie 2026 22:19:31
Problema Componente tare conexe Scor 0
Compilator py Status done
Runda Arhiva educationala Marime 1.38 kb
import sys
sys.setrecursionlimit(300000)

def ctc(lista, lista_inversa):
    ordine_terminare = []
    vizitat = [False] * len(lista)

    def dfs(nod):
        vizitat[nod] = True
        for vecin in lista[nod]:
            if vizitat[vecin] is False:
                dfs(vecin)
        ordine_terminare.append(nod)

    def dfs_inversat(nod):
        vizitat[nod] = True
        bloc_momentan.append(nod)
        for vecin in lista_inversa[nod]:
            if vizitat[vecin] is False:
                dfs_inversat(vecin)

    for nod in range(1, len(lista)):
        if not vizitat[nod]:
            dfs(nod)

    vizitat[:] = [False] * len(lista)

    bloc_momentan = []
    componente = []
    for nod in reversed(ordine_terminare):
        if vizitat[nod] is False:
            bloc_momentan = []
            dfs_inversat(nod)
            componente.append(bloc_momentan[:])

    return componente

with open("ctc.in") as f, open("ctc.out", "w") as g:

    N,M=map(int, f.readline().strip().split())
    lista=[[] for i in range(N+1)]
    lista_inversa=[[] for i in range(N+1)]
    for _ in range(M):
        x,y=map(int, f.readline().strip().split())
        lista[x].append(y)
        lista_inversa[y].append(x)

    rez=ctc(lista, lista_inversa)
    g.write(f"{len(rez)}\n")
    for comp in rez:
        g.write(' '.join(map(str,sorted(comp))) + '\n')