Cod sursa(job #2935812)

Utilizator Eric24ERIC ALEXANDRU MOROSAN Eric24 Data 7 noiembrie 2022 16:16:43
Problema Componente tare conexe Scor 30
Compilator py Status done
Runda Arhiva educationala Marime 1.44 kb
from collections import deque


# o problema de tare conexitate presupune existe un drum de la x la y in G
# si un drum de la y la x in G <=> exista un drum de la x la y in G transpus
# o sa verificam asta



with open("ctc.in", 'r') as f:
    n, m = f.readline().split()
    n = int(n)
    m = int(m)
    final = []
    vizitat = [0 for _ in range(n + 1)]
    adiacenta = [[] for _ in range(n + 1)]
    adiacenta_t = [[] for _ in range(n + 1)]
    componente_tari_conexe = [[] for _ in range(n + 1)]
    for i in range(m): #tinem adiacenta atat in G, cat si in G transpus
        x, y = f.readline().split()
        adiacenta[int(x)].append(int(y))
        adiacenta_t[int(y)].append(int(x))
        nr = 0


def DFS(x):
    vizitat[x] = 1
    for t in adiacenta[x]:
        if vizitat[t] == 0:
            DFS(t)
    final.append(x) # tinem evidenta nodurilor vizitate pentru a apela si dfs in G transpus

def DFS_T(x):
    vizitat[x] = 2 # asta inseamna ca nodul se afla in componenta conexa tare specifica
    componente_tari_conexe[nr].append(x)
    for t in adiacenta_t[x]:
        if vizitat[t] == 1:
            DFS_T(t)


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

while final:
    nod = final.pop()
    if vizitat[nod] == 1:
        nr += 1
        DFS_T(nod)

with open("ctc.out", 'w') as f:
    print(nr, file=f)
    for i in range(1, nr+1):
        print(*componente_tari_conexe[i], file=f)