Cod sursa(job #3375090)

Utilizator PuternicDezvoltatPuternicSRL PuternicDezvoltat Data 10 noiembrie 2026 12:21:13
Problema Componente tare conexe Scor 0
Compilator py Status done
Runda Arhiva educationala Marime 1.57 kb
#https://www.infoarena.ro/problema/ctc
#Complexitate : O(n + m) garantat de alg lui kosarajus

data = []
with open('ctc.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):
    i, j = data[2 + 2 * t], data[3 + 2 * t]
    relatii[i].append(j)
# print(relatii)
visited = [False] * (n+1)

def dfs(nod, stiva):
    visited[nod] = True
    for vecin in relatii[nod]:
        if visited[vecin] == False:
            dfs(vecin, stiva)
    stiva.append(nod)

lista = []
for i in range(1, n + 1):
    if visited[i] == False:
        dfs(i, lista)
# print(lista)
##partea acum in care mergem in ordinea inversa si gasim componentele conexe mi-a dat claudiu  https://www.geeksforgeeks.org/c/kosarajus-algorithm-in-c/
def reverse_relatii(orig,new_one):
    for nod in range(1,n+1):
        for muchie in orig[nod]:
            new_one[muchie].append(nod)
reversed_dict= {}
for i in range(1, n + 1):
    reversed_dict[i] = []
reverse_relatii(relatii,reversed_dict)
# print(reversed_dict)

visited = [False] * (n+1)

def dfsv2(nod, stiva):
    visited[nod] = True
    for vecin in reversed_dict[nod]:
        if visited[vecin] == False:
            dfsv2(vecin, stiva)
    stiva.append(nod)
contor = 0
fin = []
for i in reversed(lista):
    lista2 = []
    if visited[i] == False:
        dfsv2(i, lista2)
    if lista2 != []:
        fin.append(lista2)
        contor += 1

with open('ctc.out', 'w') as g:
    g.write(str(contor) + "\n")
    for l in fin:
        g.write(" ".join(map(str, l)) + "\n")