Pagini recente » Cod sursa (job #2629460) | Cod sursa (job #2185118) | Cod sursa (job #2623588)
# Python3 program to print DFS traversal
# from a given given graph
from collections import defaultdict
class Graph:
# init function to declare class variables
def __init__(self,V):
self.V = V
self.adj = [[] for i in range(V)]
def DFSUtil(self, temp, v, visited):
# Mark the current vertex as visited
visited[v] = True
# Store the vertex to list
temp.append(v)
# Repeat for all vertices adjacent
# to this vertex v
for i in self.adj[v]:
if visited[i] == False:
# Update the list
temp = self.DFSUtil(temp, i, visited)
return temp
# method to add an undirected edge
def addEdge(self, v, w):
self.adj[v].append(w)
self.adj[w].append(v)
# Method to retrieve connected components
# in an undirected graph
def connectedComponents(self):
visited = []
cc = []
for i in range(self.V):
visited.append(False)
for v in range(self.V):
if visited[v] == False:
temp = []
cc.append(self.DFSUtil(temp, v, visited))
return cc
# Driver Code
f1 = open("dfs.in","r")
f2 = open("dfs.out","w")
n,m = f1.readline().split()
n = int(n)
m = int(m)
graf = Graph(n)
for i in range(m):
a,b = f1.readline().split()
a = int(a)
b = int(b)
graf.addEdge(a,b)
nr = len(graf.connectedComponents())
f2.write(str(nr))