Cod sursa(job #2303153)

Utilizator 24601Dan Ban 24601 Data 15 decembrie 2018 18:57:26
Problema Parcurgere DFS - componente conexe Scor 65
Compilator py Status done
Runda Arhiva educationala Marime 0.88 kb
def main():
    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):
        if v in visited:
            return 0

        stk = [v, ]

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

        return 1

    result = sum(map(lambda v: dfs(v + 1), range(n)))

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

if __name__ == '__main__':
    main()