Cod sursa(job #2284106)

Utilizator 24601Dan Ban 24601 Data 16 noiembrie 2018 19:56:39
Problema Parcurgere DFS - componente conexe Scor 0
Compilator py Status done
Runda Arhiva educationala Marime 0.9 kb
@profile
def do():
    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)

    @profile
    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]:
                        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)

do()