Cod sursa(job #2623575)

Utilizator RaduhhRadu Flocea Raduhh Data 3 iunie 2020 14:07:44
Problema Parcurgere DFS - componente conexe Scor 10
Compilator py Status done
Runda Arhiva educationala Marime 1.59 kb
# 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))