Cod sursa(job #2284092)

Utilizator 24601Dan Ban 24601 Data 16 noiembrie 2018 19:36:30
Problema Parcurgere DFS - componente conexe Scor 60
Compilator py Status done
Runda Arhiva educationala Marime 0.66 kb
with open('dfs.in') as fp:
    n, _ = list(map(int, fp.readline().strip().split()))

    adj_list = {}
    visited = [False, ] * (n + 1)

    for line in fp:
        u, v = list(map(int, line.strip().split()))

        if u not in adj_list:
            adj_list[u] = []

        if v not in adj_list:
            adj_list[v] = []

        adj_list[u].append(v)
        adj_list[v].append(u)

def dfs(v):
    visited[v] = True

    if v not in adj_list:
        return

    for u in adj_list[v]:
        if not visited[u]:
            dfs(u)

result = 0

for v in range(1, n + 1):
    if not visited[v]:
        dfs(v)
        result += 1

open('dfs.out', 'w').write(str(result))