Cod sursa(job #2937084)

Utilizator marinee.anca17@yahoo.comChiricuta Marina Anca [email protected] Data 9 noiembrie 2022 21:24:46
Problema Componente tare conexe Scor 0
Compilator py Status done
Runda Arhiva educationala Marime 1.01 kb
from typing import List

def DFS(nod: int, lista_adiacenta: List[List[int]], vizitate: List[int], stiva: List[int]) -> None:
  vizitate[nod] = 1
  for item in lista_adiacenta[nod]:
    if not vizitate[item]:
      DFS(item, lista_adiacenta, vizitate, stiva)
  stiva.append(nod)

def componenteTareConexe(nr_noduri: int, arce: List[List[int]]) -> List[List[int]]:
  vizitate = [0 for _ in range(nr_noduri + 1)]
  lista_adiacenta = [[] for _ in range(nr_noduri + 1)]
  lista_adiacenta_Tr = [[] for _ in range(nr_noduri + 1)]

  for arc in arce:
    lista_adiacenta[arc[0]].append(arc[1])
    lista_adiacenta_Tr[arc[1]].append(arc[0])
  
  stiva = []
  for nod in range(1, nr_noduri + 1):
    if not vizitate[nod]:
      DFS(nod, lista_adiacenta, vizitate, stiva)
  
  vizitate = [0 for _ in range(nr_noduri + 1)]
  rezultat = []
  while len(stiva) > 0:
    nod = stiva.pop()
    if not vizitate[nod]:
      componenta = []
      DFS(nod, lista_adiacenta_Tr, vizitate, componenta)
      rezultat.append(componenta)

  return rezultat