Cod sursa(job #2449073)

Utilizator voyagerSachelarie Bogdan voyager Data 18 august 2019 01:09:46
Problema Parcurgere DFS - componente conexe Scor 60
Compilator py Status done
Runda Arhiva educationala Marime 0.6 kb
#!/usr/bin/env python3

import sys

sys.stdout = open('dfs.out', 'w')

with open('dfs.in', 'r') as fin:
    readInts = lambda: tuple(map(int, fin.readline().split()))
    N, M = readInts()
    edges = [[] for _ in range(N + 1)]
    visited = [False] * (N + 1)
    for _ in range(M):
        s, t = readInts()
        edges[s].append(t)
        edges[t].append(s)

    def visit(x):
        if visited[x]: return
        visited[x] = True

        for t in edges[x]:
            visit(t)

    cc = 0
    for n in range(1, N + 1):
        if not visited[n]:
            cc += 1
            visit(n)

    print(cc)