Cod sursa(job #2927874)

Utilizator pasare.franci@yahoo.comPasare Francisca [email protected] Data 21 octombrie 2022 18:33:55
Problema Componente tare conexe Scor 0
Compilator py Status done
Runda Arhiva educationala Marime 2.07 kb
import sys
sys.setrecursionlimit(1000001)
f = open("ctc.in")
line = f.readline()
v = line.split()
n = int(v[0])  #nr varfuri
m = int(v[1])  #nr muchii
lista=[]
stv=[]
#construire matrice de adiacenta
def citire_matrice_liste(noduri, muchii, orientat):
    l = {}
    for i in range(1, noduri + 1):
        l[i] = []

    for i in range(muchii):
        line = f.readline()
        v = line.split()
        if orientat:
            l[int(v[0])].append(int(v[1]))
        else:
            l[int(v[0])].append(int(v[1]))
            l[int(v[1])].append(int(v[0]))
    return l
#lista este matricea de adiacenta
lista = citire_matrice_liste(n, m, 1)

#facem dfs grafului G
def Dfs(nod,visited_vertex,lista):
    visited_vertex[nod] = 1
    global stv
    stv.append(nod)
    for vecin in lista[nod]:
        if visited_vertex[vecin]==0:
             Dfs(vecin,visited_vertex,lista)

# introducem intr-o stiva la momentul finalizat (penttu a a obtine o ordine descrescatoare)
def fill_order(nod,visited_vertex, stack):
    visited_vertex[nod] = 1
    for vecin in lista[nod]:
        if visited_vertex[vecin]==0:
            fill_order(vecin,visited_vertex, stack)
    stack = stack.append(nod)

# facem G^t
def transpose():
    g = {}
    for i in range(1, n + 1):
        g[i] = []
    for i in lista:
        for j in lista[i]:
            g[j].append(i)
    return g

#afisam componentele tare conexe
d={}
def print_scc():
    global d,stv
    nr=0
    stack = []
    visited_vertex = [0] * (n+1)
    for i in range(1, n + 1):
        if visited_vertex[i]==0:
            fill_order(i,visited_vertex, stack)

    gr = transpose()

    visited_vertex = [0] * (n + 1)

    while stack:
        i = stack.pop()
        if visited_vertex[i]==0:
            nr=nr+1
            Dfs(i,visited_vertex,gr)
            d[nr]=[]
            for i in stv:
                d[nr].append(i)
            stv=[]

print_scc()
g=open("ctc.out","w")
g.write(str(len(d))+"\n")
for x in d:
    for i in d[x]:
        g.write(str(i)+" ")
    g.write("\n")