Cod sursa(job #3164152)

Utilizator bianca.iscBianca Iscru bianca.isc Data 2 noiembrie 2023 11:41:27
Problema Parcurgere DFS - componente conexe Scor 0
Compilator py Status done
Runda Arhiva educationala Marime 0.93 kb
def dfs(nod):
    viz[nod - 1] = 1
    for next in g[nod - 1]:
        if viz[next - 1] == 0:
            dfs(next)

    stiva.append(nod)

def dfs_t(nod):
    scc.append(nod)
    viz[nod - 1] = 1
    for next in gt[nod - 1]:
        if viz[next - 1] == 0:
            dfs_t(next)

linie = input().strip().split()
n, m = int(linie[0]), int(linie[1])

g = [[] for _ in range(n)]
gt = [[] for _ in range(n)]
viz = [0] * n
stiva = []
ctc = []


for i in range(m):
    linie = input().strip().split()
    x, y = int(linie[0]), int(linie[1])
    g[x - 1].append(y)
    gt[y - 1].append(x)

for i in range(1, n + 1):
    if viz[i - 1] == 0:
        dfs(i)

viz = [0] * n

while stiva:
    x = stiva.pop()

    if viz[x - 1] == 0:
        scc = []
        dfs_t(x)
        ctc.append(scc)

print(len(ctc))

#count = 0
#for comp in ctc:
 #   count += 1
  #  for el in comp:
   #     print(count, end=" ")