Cod sursa(job #2303146)

Utilizator 24601Dan Ban 24601 Data 15 decembrie 2018 18:41:16
Problema Parcurgere DFS - componente conexe Scor 65
Compilator py Status done
Runda Arhiva educationala Marime 0.96 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):
        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)

if __name__ == '__main__':
    main()