Cod sursa(job #2284116)

Utilizator 24601Dan Ban 24601 Data 16 noiembrie 2018 20:08:59
Problema Parcurgere DFS - componente conexe Scor 65
Compilator py Status done
Runda Arhiva educationala Marime 0.79 kb
with open('dfs.in') as fp:
    n = int(fp.readline().split()[0])

    adj_list = {}
    visited = set()

    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):
    stk = []
    stk.append(v)

    while stk:
        v = stk.pop()
        if v not in visited:
            visited.add(v)
            if v in adj_list:
                for u in adj_list[v]:
                    if u not in visited:
                        stk.append(u)

result = 0

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

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