Cod sursa(job #2783086)

Utilizator Andrei_SturzuAndrei Sturzu Andrei_Sturzu Data 13 octombrie 2021 19:19:48
Problema Parcurgere DFS - componente conexe Scor 20
Compilator py Status done
Runda Arhiva educationala Marime 1.13 kb
class Graph:

    def __init__(self, nodes):
        self.nodes = nodes
        self.neighbours = [[] for _ in range(self.nodes)]

    def addUndirectedEdge(self, u, v):
        self.neighbours[u].append(v)
        self.neighbours[v].append(u)

    def dfs(self, node, visited):
        visited[node] = True

        for i in self.neighbours[node]:
            if not visited[i]:
                self.dfs(i, visited)

    def NumberOfconnectedComponents(self):
        visited = [False] * self.nodes

        count = 0

        for node in range(self.nodes):
            if not visited[node]:
                self.dfs(node, visited)
                count += 1

        return count


file = 'dfs.in'

with open(file, 'rt') as f:
    content = f.readlines()
    content = [line.strip().split() for line in content]
    content = [[int(x) for x in line] for line in content]
    N, M = content[0][0], content[0][1]

g = Graph(N)
for edges in content[1:]:
    g.addUndirectedEdge(edges[0], edges[1])

result = g.NumberOfconnectedComponents()

with open('dfs.out', 'wt') as f:
    f.write(str(result))