Cod sursa(job #3371540)

Utilizator david18.6yDavid Popa david18.6y Data 30 octombrie 2026 18:31:33
Problema Componente tare conexe Scor 0
Compilator py Status done
Runda Arhiva educationala Marime 1.72 kb
from collections import deque

def ctc(lista):
    lista_compl=[[] for i in range(len(lista))]
    for i, noduri in enumerate(lista):
        for nod in noduri:
            lista_compl[nod].append(i)

    deja_in_comp=[False]*len(lista)
    componente=[]

    for nod in range(1,len(lista)):
        if deja_in_comp[nod]:continue

        plus=set([nod])
        vazut_plus=[False]*(len(lista))
        coada=deque([nod])
        while coada:
            varf=coada.popleft()
            vazut_plus[varf]=True
            for vecin in lista[varf]:
                if vazut_plus[vecin] is False:
                    plus.add(vecin)
                    coada.append(vecin)
                    vazut_plus[vecin]=True

        minus = set([nod])
        vazut_minus = [False] * (len(lista))
        coada = deque([nod])
        while coada:
            varf = coada.popleft()
            vazut_minus[varf]=True
            for vecin in lista_compl[varf]:
                if vazut_minus[vecin] is False:
                    minus.add(vecin)
                    coada.append(vecin)
                    vazut_minus[vecin] = True

        componenta_lui_nod=set([])
        componenta_lui_nod = plus&minus

        componente.append(componenta_lui_nod)

        for x in componenta_lui_nod:
            deja_in_comp[x]=True

    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)]
    for _ in range(M):
        x,y=map(int, f.readline().strip().split())
        lista[x].append(y)

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