Cod sursa(job #2623568)

Utilizator RaduhhRadu Flocea Raduhh Data 3 iunie 2020 13:56:21
Problema Parcurgere DFS - componente conexe Scor 50
Compilator py Status done
Runda Arhiva educationala Marime 0.75 kb
from collections import defaultdict 
  
class Graph: 
  
    def __init__(self):
        self.viz = [0]*100000
        self.graph = defaultdict(list) 
  
    def addEdge(self, u, v): 
        self.graph[u].append(v) 

    def dfs(self, node):
        self.viz[node] = 1
        for i in self.graph[node]:
            if self.viz[i]==0:
                self.dfs(i)


graf = Graph()

f1 = open("dfs.in","r")
f2 = open("dfs.out","w")


n,m = f1.readline().split()
n = int(n)
m = int(m)

for i in range(m):
    a,b = f1.readline().split()
    a = int(a)
    b = int(b)
    graf.addEdge(a,b)
    graf.addEdge(b,a)

    
    
nr = 0
for i in range(1,n+1):
    if graf.viz[i]==0:
        graf.dfs(i)
        nr+=1

f2.write(str(nr))