Cod sursa(job #2606364)

Utilizator lev.tempfliTempfli Levente lev.tempfli Data 27 aprilie 2020 16:28:06
Problema Parcurgere DFS - componente conexe Scor 60
Compilator py Status done
Runda Arhiva educationala Marime 1.06 kb
import math
import queue


def input_gen_int(fnmae):
    with open(fnmae, 'rt') as fin:
        for line in fin:
            for val in line.split():
                yield int(val)


class Graph:
    n = 0
    m = 0
    adj_list = []

    def __init__(self, ig):
        self.n, self.m = next(ig), next(ig)
        self.adj_list = [[] for _ in range(self.n + 1)]

        for _ in range(self.m):
            f, g = next(ig), next(ig)
            self.adj_list[f].append(g)
            self.adj_list[g].append(f)

    def num_conn_comp(self):
        seen = [0 for _ in range(self.n + 1)]
        k = 0
        for i in range(1, self.n + 1):
            if seen[i] == 0:
                k += 1
                self.dfs(i, seen)
        return k

    def dfs(self, k, seen):
        if seen[k] == 1:
            return
        seen[k] = 1
        for i in self.adj_list[k]:
            self.dfs(i, seen)


if __name__ == "__main__":
    ig = input_gen_int("dfs.in")
    graph = Graph(ig)

    with open("dfs.out", 'wt') as fout:
        fout.write('{} '.format(graph.num_conn_comp()))