Pagini recente » Cod sursa (job #1918242) | Cod sursa (job #2598737) | Cod sursa (job #1437617) | Cod sursa (job #891466) | Cod sursa (job #2935812)
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)