Cod sursa(job #2533356)

Utilizator TeodorCotetCotet Teodor TeodorCotet Data 28 ianuarie 2020 22:16:04
Problema Parcurgere DFS - componente conexe Scor 50
Compilator py Status done
Runda Arhiva educationala Marime 0.84 kb
import math, queue

def read_gen(fname):
    with open(fname, 'rt') as fin:
        for line in fin:
            for val in line.split():
                yield int(val)

def dfs(x, g, used):
    used[x] = True
    for node in g[x]:
        if used[node] == False:
            dfs(node, g, used)

def solve(n, g):
    cnt_comp = 0
    used = {x: False for x in range(1, n + 1)}
    for i in range(1, n + 1):
        if used[i] is False:
            cnt_comp += 1
            dfs(i, g, used)
    return cnt_comp

if __name__ == "__main__":
    it = read_gen('dfs.in')
    n, m = next(it), next(it)
    g = {x: [] for x in range(1, n + 1)}
   
    for _ in range(m):
        x, y = next(it), next(it)
        g[x].append(y)
        g[y].append(x)
    
    cnt_comp = solve(n, g)
    with open('dfs.out', 'wt') as fout:
        fout.write('{}\n'.format(cnt_comp))