Cod sursa(job #2697080)

Utilizator Oana2001Atasie Oana-Andreea Oana2001 Data 17 ianuarie 2021 17:26:38
Problema Componente biconexe Scor 0
Compilator py Status done
Runda Arhiva educationala Marime 1.69 kb
from collections import deque

def citire_graf(tip_graf=False): # Nu este FALSE sau false
    n=0
    fisier=open("BiconexC.in","r")
    prima_linie=fisier.readline() # citim prima linie din fisier
    n_m=prima_linie.split() # aici avem nodurile si muchiile intr-un array de siruri
    n=int(n_m[0])
    m=int(n_m[1])
    la=[[] for i in range(n)] # la=n*[[]] NU e ok, sunt aceeasi lista
    for muchie in fisier:
        x,y=(int(z) for z in muchie.split())
        x-=1
        y-=1 # scadem un 1 din nr. varfului deoarece in rest o sa mergem de la 0
        la[x].append(y)
        if tip_graf == False:
            la[y].append(x)
    return n,la


def afisare_lista(la):
    for i in range(0,len(la)):
        for j in range(0,len(la[i])):
            print(str(i+1)+" "+str(la[i][j]+1))  # cu str aduci la sir de caractere



n, la = citire_graf()
viz=[0]*n
niv=[None]*n
niv_min=[None]*n
global nr
S=deque()

def df(x):
    global nr
    viz[x] = 1
    niv_min[x] = niv[x]
    for y in la[x]:
        if viz[y] == 0:
            niv[y] = niv[x]+1
           # print(x+1,y+1)
            S.append((x+1,y+1))
            df(y)
            niv_min[x] = min(niv_min[x],niv_min[y])
            # verificare componenta biconexa
            if niv_min[y] >= niv[x]:
                w = -1
                while w !=(x+1,y+1):
                    w = S.pop()
                    print(w)
                print(" ")
                # S.append((x+1,y+1))
        else:
            if niv[y] < niv[x]-1:
                niv_min[x] = min(niv_min[x], niv[y])
                S.append((x+1,y+1))


niv[1] = 1
df(1)
for i in range(n):
    if viz[i]!=0:
        df(i)
# print(S)