Cod sursa(job #2797456)

Utilizator PopelEmilBogdanPopel Emil-Bogdan PopelEmilBogdan Data 9 noiembrie 2021 22:04:34
Problema Parcurgere DFS - componente conexe Scor 60
Compilator py Status done
Runda Arhiva educationala Marime 1.05 kb
from collections import defaultdict

with open("dfs.in", 'r') as f:
    lines = f.readlines()
    N, M = [int(val) for val in lines[0].split()]
f.close()


class Graph:
    def __init__(self):
        self.graph = defaultdict(list)


    def addEdge(self, u, v):
        self.graph[u].append(v)


    def DFS(self, visited, nod_curent):
        visited[nod_curent] = True
        for i in range(0, len(self.graph[nod_curent])):
            if not visited[ self.graph[nod_curent][i] ]:
                g.DFS(visited, self.graph[nod_curent][i])


    def Componente_Conexe(self):
        contor = 0;
        visited = [False] * (N+1)

        for i in range(1, N+1):
            if not visited[i]:
                g.DFS(visited, i)
                contor += 1
        return contor


g = Graph()
for i in range(1, M + 1):
    node1, node2 = [int(val) for val in lines[i].split()]
    g.addEdge(node1, node2)
    g.addEdge(node2, node1)

with open("dfs.out", 'w') as fout:
    fout.write('%s ' % g.Componente_Conexe())
fout.close()