Pagini recente » Cod sursa (job #1048125) | Cod sursa (job #1857611) | Cod sursa (job #1631186) | Cod sursa (job #2745391) | Cod sursa (job #2937297)
# MEREALBE BRIANA, 243
# COMPONENTE TARE CONEXE
import sys
f = open("ctc.in")
linie = f.readline()
linie = linie.split()
n = int(linie[0]) # nr noduri
m = int(linie[1]) # nr muchii
lista_muchii = []
for i in range(0, m):
linie = f.readline()
linie = linie.split()
p = []
for j in linie:
p.append(int(j))
lista_muchii.append(p)
def DFS(nod: int, lista_adiacenta: list[list[int]], vizitate: list[int], stack: list[int]) -> None:
vizitate[nod] = 1
for n in lista_adiacenta[nod]:
if not vizitate[n]:
DFS(n, lista_adiacenta, vizitate, stack)
stack.append(nod)
#algoritmul lui Kosaraju:
def ctc(n: int, lista_muchii: list[list[int]]) -> list[list[int]]:
vizitate1 = [0 for i in range(n + 1)]
lista_adiacenta = [[] for i in range(n + 1)]
lista_adiacenta_inversata = [[] for i in range(n + 1)]
for muchie in lista_muchii:
lista_adiacenta[muchie[0]].append(muchie[1])
lista_adiacenta_inversata[muchie[1]].append(muchie[0])
stack = []
for nod in range(1, n + 1):
if not vizitate1[nod]:
DFS(nod, lista_adiacenta, vizitate1, stack)
vizitate2 = [0 for i in range(n + 1)]
rezultat = []
while len(stack) > 0:
nod = stack.pop()
if not vizitate2[nod]:
componenta = []
DFS(nod, lista_adiacenta_inversata, vizitate2, componenta)
rezultat.append(componenta)
return rezultat
solutie = ctc(n,lista_muchii)
with open('ctc.out', 'w') as f:
print(len(solutie), file=f)
for i in range(len(solutie)):
solutie[i].sort()
print(*solutie[i], file=f)