Cod sursa(job #2712586)

Utilizator conttestecontteste12345 contteste Data 26 februarie 2021 06:26:59
Problema Parcurgere DFS - componente conexe Scor 50
Compilator py Status done
Runda Arhiva educationala Marime 1.62 kb
class FunnyGraph:

    def __init__(self):
        self.istream = open("dfs.in", "r")
        self.ostream = open("dfs.out", "w")
        self.visited = set()
        self.__read_graph()
        self.__build_graph()        
        self.ostream.write(str(self.__dfs_components(1))) 


    def __read_graph(self):
        self.lines = self.istream.readlines()
        self.n, self.m = list(map(int, self.lines[0].strip().split()))
        self.lines = self.lines[1:]
        print(self.n, self.m)


    def __build_graph(self):
        self.graph = {}

        for i in range(1, self.n+1):
            self.graph[i] = []

        for line in self.lines:
            pair = line.strip().split()
            pair = [int(pair[0]), int(pair[1])]
            self.graph[pair[0]].append(pair[1])
            self.graph[pair[1]].append(pair[0])

        print(self.graph)


    def __dfs(self, node):
        stack = [node]

        while len(stack) > 0:
            node = stack.pop()
            if node in self.visited:
                continue
            self.visited.add(node)
            print("Node: {}".format(node))

            for neighbour in self.graph[node]:
                if neighbour not in self.visited:
                    stack.append(neighbour)


    def __dfs_components(self, node):
        number_of_components = 0

        for i in range(1, self.n + 1):
            if i not in self.visited:
                print("------------------------------------------------------------------")
                self.__dfs(i)
                print(self.visited)
                number_of_components += 1

        return number_of_components

FunnyGraph()