Cod sursa(job #3372061)

Utilizator david18.6yDavid Popa david18.6y Data 2 noiembrie 2026 14:31:28
Problema Componente biconexe Scor 80
Compilator py Status done
Runda Arhiva educationala Marime 1.85 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
        if(ordine[nod]==0):

            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)):
        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(str(x) for x in list(c)) + "\n")