Pagini recente » Cod sursa (job #2699274) | Cod sursa (job #2629465) | Cod sursa (job #1950059) | Cod sursa (job #2623568)
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))