Cod sursa(job #2791839)

Utilizator NSA-16Neacsu-Tranciuc Sasa-Andrei NSA-16 Data 31 octombrie 2021 11:06:21
Problema Parcurgere DFS - componente conexe Scor 65
Compilator py Status done
Runda Arhiva educationala Marime 0.7 kb
import sys
sys.setrecursionlimit(10**6)
def DFS(file, file2):
    f = open(file, "r")
    g = open(file2, "w")
    n, m = [int(n) for n in f.readline().split()]
    d = {}
    for i in range(1, n + 1):
        d[i] = []
    for i in range(m):
        n1, n2 = [int(n) for n in f.readline().split()]
        d[n1].append(n2)
        d[n2].append(n1)
    r = 0
    v = (n + 1) * [False]
    def DFS_Recursie(n):
        v[n] = True
        for k in d[n]:
            if v[k] is False:
                DFS_Recursie(k)

    for i in range(1, n + 1):
        if v[i] is False:
            r += 1
            DFS_Recursie(i)
    g.write(str(r))
    f.close()
    g.close()
DFS("dfs.in", "dfs.out")