# Python program to print DFS traversal for complete graph 

from collections import defaultdict 

  
# This class represents a directed graph using adjacency 
# list representation 

class Graph: 

  

    # Constructor 

    def __init__(self): 

  

        # default dictionary to store graph 

        self.graph = defaultdict(list) 

  

    # function to add an edge to graph 

    def addEdge(self,u,v): 

        self.graph[u].append(v) 

  

    # A function used by DFS 

    def DFSUtil(self, v, visited): 

  

        # Mark the current node as visited and print it 

        visited[v]= True

        print v, 

  

        # Recur for all the vertices adjacent to 

        # this vertex 

        for i in self.graph[v]: 

            if visited[i] == False: 

                self.DFSUtil(i, visited) 

  

  

    # The function to do DFS traversal. It uses 

    # recursive DFSUtil() 

    def DFS(self): 

        V = len(self.graph)  #total vertices 

  

        # Mark all the vertices as not visited 

        visited =[False]*(V) 

  

        # Call the recursive helper function to print 

        # DFS traversal starting from all vertices one 

        # by one 

        for i in range(V): 

            if visited[i] == False: 

                self.DFSUtil(i, visited) 

  
