Cod sursa(job #3375089)

Utilizator PuternicDezvoltatPuternicSRL PuternicDezvoltat Data 10 noiembrie 2026 12:20:53
Problema Componente biconexe Scor 60
Compilator py Status done
Runda Arhiva educationala Marime 1.41 kb
#https://www.infoarena.ro/problema/biconex
#Complexitate: O(n + m) similar in rezolvare cu pamant doar ca retinem muchii aici

data = []
with open('biconex.in', 'r') as f:
    data = list(map(int, f.read().strip().split()))
n, m = data[0], data[1]

relatii = {}
for i in range(1, n + 1):
    relatii[i] = []
for t in range(m):
    x, y = data[2 + 2 * t], data[3 + 2 * t]
    relatii[x].append(y)
    relatii[y].append(x)

niv = [0] * (n + 1)
low = [0] * (n + 1) 
stiva = []
componente = []

def extrage(nod, fiu):
    comp = set()
    while True:
        a, b = stiva.pop()
        comp.add(a)
        comp.add(b)
        if a == nod and b == fiu:
            break
    componente.append(comp)

def dfs(nod, tata):
    niv[nod] = niv[tata] + 1
    low[nod] = niv[nod]
    for vecin in relatii[nod]:
        if vecin == tata:
            continue
        if niv[vecin] != 0: #vizitat
            low[nod] = min(low[nod], niv[vecin])
            if niv[vecin] < niv[nod]:
                stiva.append((nod, vecin))
        else:
            stiva.append((nod, vecin))
            dfs(vecin, nod)
            low[nod] = min(low[nod], low[vecin])
            if low[vecin] >= niv[nod]:
                extrage(nod, vecin)

for i in range(1, n + 1):
    if niv[i] == 0:
        dfs(i, 0)

with open('biconex.out', 'w') as g:
    g.write(str(len(componente)) + "\n")
    for c in componente:
        g.write(" ".join(map(str, sorted(c))) + "\n")