Cod sursa(job #3372078)

Utilizator david18.6yDavid Popa david18.6y Data 2 noiembrie 2026 14:37:35
Problema Componente biconexe Scor 80
Compilator py Status done
Runda Arhiva educationala Marime 1.75 kb
import sys
sys.setrecursionlimit(300000)


def biconex(lista):

    ordine=[0]*len(lista)
    ocolire=[0]*len(lista)
    parinte=[0]*len(lista)
    moment=0
    comp=[]
    stiva_muchii=[]

    def dfs(nod):
        nonlocal moment
        moment+=1
        ordine[nod]=moment
        ocolire[nod]=ordine[nod]
        copii_descoperiti=0

        for vecin in lista[nod]:

            if vecin==parinte[nod]:
                pass
            elif ordine[vecin]!=0:
                ocolire[nod]=min(ocolire[nod], ordine[vecin])
                if ordine[vecin] < ordine[nod]:
                    stiva_muchii.append((nod, vecin))
            else:
                parinte[vecin]=nod
                copii_descoperiti+=1
                stiva_muchii.append((nod, vecin))
                dfs(vecin)
                ocolire[nod]=min(ocolire[nod], ocolire[vecin])
                if ocolire[vecin]>=ordine[nod]:
                    componenta=set()

                    while True:
                        (nodul, vecinul)=stiva_muchii.pop()
                        componenta.add(nodul); componenta.add(vecinul)
                        if ((nodul,vecinul)==(nod,vecin)): break

                    comp.append(componenta)


    for nod in range(1, len(lista)):
        if ordine[nod] == 0:
            dfs(nod)

    return comp




with open("biconex.in") as f, open("biconex.out", "w") as g:
    N,M=map(int,f.readline().strip().split())
    lista=[[] for _ in range(N+1)]
    for _ in range(M):
        x,y=map(int,f.readline().strip().split())
        lista[x].append(y)
        lista[y].append(x)

    comp=biconex(lista)

    g.write(str(len(comp)) + "\n")
    for c in comp:
        g.write(" ".join(map(str, c)) + "\n")