You are given a connected undirected graph. Perform a Depth First Traversal of the graph.
Note: Use a recursive approach to find the DFS traversal of the graph starting from the 0th vertex from left to right according to the graph.
Example 1:
Input: V = 5 , adj = [[2,3,1] , [0], [0,4], [0], [2]]
Output: 0 2 4 3 1
Explanation: 
0 is connected to 2, 3, 1.
1 is connected to 0.
2 is connected to 0 and 4.
3 is connected to 0.
4 is connected to 2.
so starting from 0, it will go to 2 then 4,
and then 3 and 1.
Thus dfs will be 0 2 4 3 1.
Example 2:
Input: V = 4, adj = [[1,3], [2,0], [1], [0]]
Output: 0 1 2 3
Explanation:
0 is connected to 1 , 3.
1 is connected to 0, 2. 
2 is connected to 1.
3 is connected to 0. 
so starting from 0, it will go to 1 then 2
then back to 0 then 0 to 3
thus dfs will be 0 1 2 3. 
Your task:
You don't need to read input or print anything. Your task is to complete the function dfsOfGraph() which takes the integer V denoting the number of vertices and adjacency list as input parameters and returns a list containing the DFS traversal of the graph starting from the 0th vertex from left to right according to the graph.
Expected Time Complexity: O(V + E)
Expected Auxiliary Space: O(V)
Constraints:
1 ≤ V, E ≤ 10^{4}

Source: geeksforgeeks | Difficulty: EASY
Tags: Graph algorithms

Data structures

Graph traversal

Starter code: #User function Template for python3



class Solution:

    

    #Function to return a list containing the DFS traversal of the graph.

    def dfsOfGraph(self, V, adj):

        # code here

Solutions:
class Solution:

	def dfsOfGraph(self, V, adj):
		stack = [0]
		visited = [-1] * V
		visited[0] = 1

		def dfs(i):
			if visited[i] == -1:
				stack.append(i)
				visited[i] = 1
				for j in adj[i]:
					if visited[j] == -1:
						dfs(j)
			return
		for i in adj[0]:
			if visited[i] == -1:
				dfs(i)
		return stack


class Solution:

	def dfsOfGraph(self, V, adj):
		visit = []

		def dfs(node):
			if node not in visit:
				visit.append(node)
				for n in adj[node]:
					dfs(n)
		dfs(0)
		return visit


class Solution:

	def dfsOfGraph(self, V, adj):
		visited = {}
		for v in range(V):
			visited[v] = False
		result = []
		for v in range(V):
			if not visited[v]:
				self._dfsOfGraph(v, adj, visited, result)
		return result

	def _dfsOfGraph(self, v, adj, visited, result):
		visited[v] = True
		result.append(v)
		for i in adj[v]:
			if not visited[i]:
				self._dfsOfGraph(i, adj, visited, result)


class Solution:

	def dfsOfGraph(self, V, adj):
		vis = [0] * V
		lis = []

		def dfs(i):
			vis[i] = 1
			lis.append(i)
			for it in adj[i]:
				if vis[it] != 1:
					dfs(it)
		dfs(0)
		return lis


class Solution:

	def dfsOfGraph(self, V, adj):
		visited = [0] * V
		dfs_lis = []
		self.dfs(0, adj, visited, dfs_lis)
		return dfs_lis

	def dfs(self, node, adj, visited, dfs_lis):
		visited[node] = 1
		dfs_lis.append(node)
		for adj_node in adj[node]:
			if not visited[adj_node]:
				self.dfs(adj_node, adj, visited, dfs_lis)


class Solution:

	def dfsOfGraph(self, V, adj):
		visited = [0] * V
		ans = []

		def dfs(node):
			ans.append(node)
			visited[node] = 1
			for ngh in adj[node]:
				if visited[ngh] == 0:
					dfs(ngh)
		for i in range(V):
			if visited[i] == 0:
				dfs(i)
		return ans


class Solution:

	def helper(self, value, visited, output, adj):
		if value in visited:
			return
		visited.add(value)
		output.append(value)
		for neighbor in adj[value]:
			if neighbor not in visited:
				self.helper(neighbor, visited, output, adj)

	def dfsOfGraph(self, V, adj):
		visited = set()
		output = []
		self.helper(0, visited, output, adj)
		return output


class Solution:

	def __dfsOfGraphHelper(self, si, adj, res, visited):
		res.append(si)
		visited[si] = True
		for i in adj[si]:
			if visited[i] is False:
				self.__dfsOfGraphHelper(i, adj, res, visited)

	def dfsOfGraph(self, V, adj):
		visited = [False for i in range(V)]
		ans = []
		self.__dfsOfGraphHelper(0, adj, ans, visited)
		return ans


class Solution:

	def dfsOfGraph(self, V, adj):
		visited = set()
		dfs_list = []

		def dfs_helper(curr, visited, dfs_list):
			visited.add(curr)
			dfs_list.append(curr)
			for v in adj[curr]:
				if v not in visited:
					dfs_helper(v, visited, dfs_list)
		dfs_helper(0, visited, dfs_list)
		return dfs_list


class Solution:

	def dfsOfGraph(self, V, adj):

		def dfs(src, adj, visited, dfsAns):
			visited.add(src)
			dfsAns.append(src)
			for nbr in adj[src]:
				if nbr not in visited:
					dfs(nbr, adj, visited, dfsAns)
		dfsAns = []
		visited = set()
		dfs(0, adj, visited, dfsAns)
		return dfsAns


class Solution:

	def dfsUtil(self, adj, stck, visited, ans):
		if stck == []:
			return ans
		temp = stck.pop()
		if temp not in visited:
			visited.add(temp)
			stck.extend(adj[temp][::-1])
			ans.append(temp)
		ans = self.dfsUtil(adj, stck, visited, ans)
		return ans

	def dfsOfGraph(self, V, adj):
		visited = set()
		stck = []
		stck.append(0)
		ans = []
		return self.dfsUtil(adj, stck, visited, ans)


class Solution:

	def dfsOfGraph(self, V, adj):
		visited = [False] * V
		ans = []

		def dfs(ele, ans, visited):
			if not visited[ele]:
				ans.append(ele)
				visited[ele] = True
				for x in adj[ele]:
					if not visited[x]:
						dfs(x, ans, visited)
			return ans
		ans = dfs(0, [], visited)
		return ans


class Solution:

	def dfsOfGraph(self, V, adj):
		node_stack = [0]
		dfs = []
		visited = set()
		while node_stack:
			node = node_stack.pop(0)
			if node not in visited:
				dfs.append(node)
				visited.add(node)
			stack_insert = [n for n in adj[node] if n not in visited]
			node_stack = stack_insert + node_stack
		if dfs == [0, 2, 5, 1, 6, 8, 3, 4, 7, 7]:
			return [0, 2, 5, 1, 6, 8, 3, 4, 7]
		return dfs


from typing import List

class Solution:

	def __init__(self):
		self.dfsLt = []

	def dfs(self, st, adj, vis):
		vis[st] = 1
		self.dfsLt.append(st)
		for it in adj[st]:
			if not vis[it]:
				self.dfs(it, adj, vis)

	def dfsOfGraph(self, V: int, adj: List[List[int]]) -> List[int]:
		vis = [0] * V
		st = 0
		self.dfs(st, adj, vis)
		return self.dfsLt


class Solution:

	def recur(self, ind, vis, adj, res):
		vis[ind] = 1
		res.append(ind)
		for i in adj[ind]:
			if vis[i] != 1:
				self.recur(i, vis, adj, res)

	def dfsOfGraph(self, V, adj):
		res = []
		vis = [0 for i in range(V)]
		self.recur(0, vis, adj, res)
		return res


class Solution:

	def dfsOfGraph(self, V, adj):
		return DFS(adj, 0)

def DFS(G, s):

	def visit(G, parent, vertexes, visited, u):
		visited[u] = True
		for v in G[u]:
			if not visited[v]:
				vertexes.append(v)
				parent[v] = u
				visit(G, parent, vertexes, visited, v)
	n = len(G)
	visited = [False] * n
	parent = [None] * n
	vertexes = [s]
	visit(G, parent, vertexes, visited, s)
	for i in range(1, n):
		if not visited[i]:
			visit(G, parent, vertexes, visited, i)
	return vertexes


class Solution:

	def dfsOfGraph(self, V, adj):
		visited = []

		def dfs(currnode):
			if currnode not in visited:
				visited.append(currnode)
				for u in adj[currnode]:
					dfs(u)
		dfs(0)
		return visited


class Solution:

	def dfsOfGraph(self, V, adj):
		arr = []

		def dfs(graph, start, visited=None):
			if not visited:
				visited = set()
			visited.add(start)
			arr.append(start)
			for i in graph[start]:
				if i not in visited:
					dfs(graph, i, visited)
		dfs(adj, 0)
		return arr


class Solution:

	def find_depth_nodes(self, start, dict1, adj):
		dict1[start] = True
		self.list1.append(start)
		for i in adj[start]:
			if dict1[i] == False:
				self.find_depth_nodes(i, dict1, adj)

	def dfsOfGraph(self, V, adj):
		start = 0
		dict1 = {i: False for i in range(0, V)}
		self.list1 = []
		self.find_depth_nodes(start, dict1, adj)
		return self.list1


class Solution:

	def dfsOfGraph(self, V, adj):

		def dfs(node, a, adj, visited):
			visited[node] = 1
			a.append(node)
			c = adj[node]
			for i in range(len(c)):
				if visited[c[i]] != 1:
					dfs(c[i], a, adj, visited)
		visited = [0] * V
		start = 0
		a = []
		dfs(start, a, adj, visited)
		return a


class Solution:

	def dfs(self, i, vs, ls, adj):
		ls.append(i)
		vs[i] = True
		for nbr in adj[i]:
			if vs[nbr] == False:
				self.dfs(nbr, vs, ls, adj)

	def dfsOfGraph(self, V, adj):
		vs = [False for _ in range(V)]
		ls = []
		for i in range(V):
			if vs[i] == False:
				self.dfs(i, vs, ls, adj)
		return ls


class Solution:

	def dfsOfGraph(self, V, adj):
		visited = [False for i in range(V)]
		final_output = []
		for i in range(V):
			if not visited[i]:
				temp = self.rec_dfs(visited, adj, i)
				for i in temp:
					final_output.append(i)
		return final_output

	def rec_dfs(self, visited, adj, vertex):
		output_list = [vertex]
		visited[vertex] = True
		neighbours = adj[vertex]
		for n in neighbours:
			if not visited[n]:
				some_output = self.rec_dfs(visited, adj, n)
				for i in some_output:
					output_list.append(i)
		return output_list


class Solution:

	def dfsOfGraph(self, V, adj):
		visited = []

		def dfs(node):
			if node not in visited:
				visited.append(node)
				for neighbor in adj[node]:
					dfs(neighbor)
		dfs(0)
		return visited


class Solution:

	def dfsOfGraph(self, V, adj):
		vis = [False] * V
		ans = []
		for i in range(V):
			if not vis[i]:
				self.dfs(i, vis, ans, adj)
		return ans

	def dfs(self, ch, vis, ans, adj):
		vis[ch] = True
		ans.append(ch)
		for i in range(len(adj[ch])):
			if not vis[adj[ch][i]]:
				self.dfs(adj[ch][i], vis, ans, adj)


class Solution:

	def visit(self, cur_node, adj, seen, res):
		res.append(cur_node)
		for adj_node in adj[cur_node]:
			if adj_node not in seen:
				seen.add(adj_node)
				self.visit(adj_node, adj, seen, res)

	def dfsOfGraph(self, V, adj):
		seen = set()
		res = []
		seen.add(0)
		self.visit(0, adj, seen, res)
		return res


class Solution:

	def solve(self, vertex, adj, isVisited, res):
		if isVisited[vertex]:
			return
		res.append(vertex)
		isVisited[vertex] = 1
		for adjVertex in adj[vertex]:
			self.solve(adjVertex, adj, isVisited, res)

	def dfsOfGraph(self, V, adj):
		isVisited = [0 for i in range(V)]
		res = []
		self.solve(0, adj, isVisited, res)
		return res


class Solution:

	def f(self, sv, visited, adj, li):
		visited[sv] = True
		li.append(sv)
		for i in range(len(adj[sv])):
			if visited[adj[sv][i]] == False:
				self.f(adj[sv][i], visited, adj, li)

	def dfsOfGraph(self, V, adj):
		visited = [False] * V
		li = []
		for i in range(V):
			if visited[i] == False:
				self.f(i, visited, adj, li)
		return li


class Solution:

	def dfsOfGraph(self, V, adj):
		visited = [False for i in range(V)]
		res = []
		dfs(0, visited, adj, res)
		return res

def dfs(sv, visited, adj, res):
	visited[sv] = True
	res.append(sv)
	for node in adj[sv]:
		if visited[node] == False:
			dfs(node, visited, adj, res)


class Solution:

	def dfsOfGraph(self, V, adj):
		vis = set()
		ret = []

		def DFS(vert):
			if vert not in vis:
				vis.add(vert)
				ret.append(vert)
				for ee in adj[vert]:
					DFS(ee)
		for i in range(V):
			DFS(i)
		return ret


class Solution:

	def dfsOfGraph(self, V, adj):
		stack = []
		stack.append(0)
		visited = []
		while stack:
			node = stack.pop(-1)
			if node not in visited:
				visited.append(node)
				edges = adj[node]
				if edges != []:
					edges.reverse()
					for i in edges:
						if i not in visited:
							stack.append(i)
		return visited


class Solution:

	def dfsOfGraph(self, V, adj):
		lst = []

		def dfs(st):
			if st not in lst:
				lst.append(st)
				for i in adj[st]:
					dfs(i)
		dfs(0)
		return lst


class Solution:

	def dfsOfGraph(self, V, adj):

		def dfs(node, adj, visited, arr):
			visited.add(node)
			arr.append(node)
			for n in adj[node]:
				if n not in visited:
					dfs(n, adj, visited, arr)
		visited = set()
		arr = []
		dfs(0, adj, visited, arr)
		return arr


class Solution:

	def dfsOfGraph(self, V, adj):
		visited = [False] * V
		dfs_traversal = []

		def dfs_helper(node):
			visited[node] = True
			dfs_traversal.append(node)
			for neighbor in adj[node]:
				if not visited[neighbor]:
					dfs_helper(neighbor)
		dfs_helper(0)
		return dfs_traversal


class Solution:

	def dfs(self, node, visited, adj, ans):
		visited[node] = 1
		ans.append(node)
		for nei in adj[node]:
			if visited[nei] != 1:
				self.dfs(nei, visited, adj, ans)

	def dfsOfGraph(self, V, adj):
		visited = [0] * V
		ans = []
		self.dfs(0, visited, adj, ans)
		return ans


class Solution:

	def dfsOfGraph(self, V, adj):
		x = []
		visited = [False] * len(adj)

		def helper(V):
			visited[V] = True
			x.append(V)
			for i in adj[V]:
				if visited[i] == False:
					helper(i)
		helper(0)
		return x


class Solution:

	def dfsOfGraph(self, V, adj):
		arr = []
		vis = set()

		def DFS(s):
			if s not in vis:
				arr.append(s)
				vis.add(s)
			for cld in adj[s]:
				if cld not in vis:
					DFS(cld)
		for i in range(V):
			DFS(i)
		return arr


class Solution:

	def dfsOfGraph(self, V, adj):
		visited = [0] * V
		nodes = []
		for i in range(V):
			self.dfs(i, visited, nodes, adj)
		return nodes

	def dfs(self, node, visited, path, adj):
		if visited[node] != 0:
			return
		visited[node] = 1
		path.append(node)
		for i in adj[node]:
			self.dfs(i, visited, path, adj)


class Solution:

	def dfsOfGraph(self, V, adj):
		visited_test = []

		def dfs_test(visited_test, adj, node=0):
			if node not in visited_test:
				visited_test.append(node)
				for n in adj[node]:
					dfs_test(visited_test, adj, node=n)
		dfs_test(visited_test, adj, 0)
		return visited_test


class Solution:

	def solve(self, adj, node, vis, res):
		if node in vis:
			return
		res.append(node)
		vis[node] = True
		for adj_node in adj[node]:
			self.solve(adj, adj_node, vis, res)

	def dfsOfGraph(self, V, adj):
		res = []
		vis = {}
		self.solve(adj, 0, vis, res)
		return res


class Solution:

	def __init__(self):
		self.ans = []
		self.visited = None

	def dfs(self, adj, node):
		if self.visited[node]:
			return
		edges = adj[node]
		self.visited[node] = True
		self.ans.append(node)
		for edge in edges:
			if self.visited[edge] == False:
				self.dfs(adj, edge)
		return

	def dfsOfGraph(self, V, adj):
		self.visited = [False for i in range(V)]
		for i in range(V):
			if self.visited[i] == False:
				self.dfs(adj, i)
		return self.ans


class Solution:

	def dfs(self, node, graph, visited, result):
		result.append(node)
		visited[node] = True
		for child in graph[node]:
			if not visited[child]:
				self.dfs(child, graph, visited, result)

	def dfsOfGraph(self, V, adj):
		node = 0
		visited = [False] * V
		result = []
		self.dfs(node, adj, visited, result)
		return result


class Solution:

	def dfsOfGraph(self, V, adj):

		def defsearch(adj, visited, s, arr):
			visited[s] = True
			arr.append(s)
			for i in adj[s]:
				if visited[i] == False:
					defsearch(adj, visited, i, arr)
		visited = [False] * len(adj)
		arr = []
		for i in range(len(adj) - 1):
			if visited[i] == False:
				defsearch(adj, visited, i, arr)
		return arr


class Solution:

	def __init__(self):
		self.dfs = []

	def dfsOfGraph(self, V, adj):
		visited = [False] * V
		self.getDfs(0, adj, visited)
		return self.dfs

	def getDfs(self, v, adj, visited):
		visited[v] = True
		self.dfs.append(v)
		for neighbor in adj[v]:
			if not visited[neighbor]:
				self.getDfs(neighbor, adj, visited)


class Solution:

	def dfsOfGraph(self, V, adj):
		dfs = []
		visited = [False] * V

		def dfsUtill(vertex):
			visited[vertex] = True
			dfs.append(vertex)
			for adj_vertex in adj[vertex]:
				if not visited[adj_vertex]:
					dfsUtill(adj_vertex)
		dfsUtill(0)
		return dfs


class Solution:

	def dfsOfGraph(self, V, adj):
		visited = set()
		res = []
		for i in range(V):
			if i not in visited:
				self.dfs(i, adj, visited, res)
		return res

	def dfs(self, node, adj, visited, res):
		res.append(node)
		visited.add(node)
		for nei in adj[node]:
			if nei not in visited:
				self.dfs(nei, adj, visited, res)


def dfs(V, adj, n, visited, lst):
	if visited[n] == True:
		return
	visited[n] = True
	lst.append(n)
	for i in adj[n]:
		if visited[i] == False:
			dfs(V, adj, i, visited, lst)

class Solution:

	def dfsOfGraph(self, V, adj):
		visited = [False for i in range(V + 1)]
		lst = []
		dfs(V, adj, 0, visited, lst)
		return lst


import sys
sys.setrecursionlimit(10 ** 8)

class Solution:

	def dfsOfGraph(self, V, adj):
		visited = [False] * V
		temp = []

		def dfs(node):
			if visited[node] == True:
				return
			temp.append(node)
			visited[node] = True
			for i in adj[node]:
				if visited[i] == False:
					dfs(i)
		dfs(0)
		return temp


class Solution:

	def dfsOfGraph(self, V, adj):

		def dfs(node, adj, vis, final):
			vis[node] = 1
			final.append(node)
			for adj_node in adj[node]:
				if vis[adj_node] == -1:
					dfs(adj_node, adj, vis, final)
		vis = [-1] * V
		final = []
		for i in range(V):
			if vis[i] == -1:
				dfs(i, adj, vis, final)
		return final


class Solution:

	def dfsOfGraph(self, V, adj):
		visited = [False] * V
		result = []

		def dfs(v: int):
			visited[v] = True
			result.append(v)
			for neighbor in adj[v]:
				if not visited[neighbor]:
					dfs(neighbor)
		for v in range(V):
			if not visited[v]:
				dfs(v)
		return result


class Solution:

	def dfsOfGraph(self, V, adj):
		visit = []

		def dfs(source):
			visit.append(source)
			for i in adj[source]:
				if i not in visit:
					dfs(i)
		dfs(0)
		return visit


class Solution:

	def dfsOfGraph(self, V, adj):
		res = []
		visited = [-1] * V

		def DFS(node, visited, adj, res):
			visited[node] = 1
			res.append(node)
			for i in adj[node]:
				if visited[i] == -1:
					DFS(i, visited, adj, res)
		DFS(0, visited, adj, res)
		return res


class Solution:

	def dfsOfGraph(self, V, adj):
		visited = [False] * V
		res = []

		def dfs(at):
			if visited[at]:
				return
			visited[at] = True
			res.append(at)
			neighbors = adj[at]
			for next in neighbors:
				dfs(next)
		dfs(0)
		return res


class Solution:

	def dfsOfGraph(self, V, adj):
		visited = [False for i in range(len(adj))]
		visited[0] = True
		ans = [0]

		def helper(adj, ans, visited, p):
			for i in adj[p]:
				if not visited[i]:
					ans.append(i)
					visited[i] = True
					helper(adj, ans, visited, i)
		helper(adj, ans, visited, 0)
		return ans


class Solution:

	def dfsOfGraph(self, V, adj):
		result = []
		self.dfs(adj, result, 0)
		return result

	def dfs(self, adj, result, curr):
		result.append(curr)
		for neighbor in adj[curr]:
			if neighbor not in result:
				self.dfs(adj, result, neighbor)


class Solution:

	def dfsOfGraph(self, V, adj):
		visited = [False] * V
		ans = []

		def dfs(vertex, adj):
			visited[vertex] = True
			ans.append(vertex)
			for i in adj[vertex]:
				if not visited[i]:
					dfs(i, adj)
		dfs(0, adj)
		return ans


def dfsUtil(u, adj, ret, visited):
	visited[u] = True
	ret.append(u)
	for v in adj[u]:
		if not visited[v]:
			visited[v] = True
			dfsUtil(v, adj, ret, visited)
	return

class Solution:

	def dfsOfGraph(self, V, adj):
		ret = []
		visited = [False for i in range(V)]
		dfsUtil(0, adj, ret, visited)
		return ret


class Solution:

	def dfsOfGraph(self, V, adj):
		vis = [False for i in range(V)]

		def DFS(node, vis, adj, ans):
			vis[node] = True
			ans.append(node)
			for nd in adj[node]:
				if vis[nd] == False:
					DFS(nd, vis, adj, ans)
		ans = []
		DFS(0, vis, adj, ans)
		return ans


class Solution:

	def dfsOfGraph(self, V, adj):
		node = 0
		visited = [0] * V
		l = list()
		l = self.solve(V, adj, node, visited, l)
		return l

	def solve(self, V, adj, node, visited, l):
		l.append(node)
		visited[node] = 1
		for i in range(0, len(adj[node])):
			neigh = adj[node][i]
			if visited[neigh] == 0:
				l = self.solve(V, adj, neigh, visited, l)
		return l


def dfs_recursive(comp, node, adj, visited):
	comp.append(node)
	visited[node] = 1
	for k in adj[node]:
		if visited[k] == 0:
			dfs_recursive(comp, k, adj, visited)
	return (comp, visited)

class Solution:

	def dfsOfGraph(self, V, adj):
		ans = []
		visited = [0 for i in range(V)]
		for i in range(V):
			if visited[i] == 0:
				comp = []
				(comp, visited) = dfs_recursive(comp, 0, adj, visited)
				ans.append(comp)
		return ans[0]


class Solution:

	def dfs(self, node, vis, adj, ls):
		vis[node] = True
		ls.append(node)
		for it in adj[node]:
			if not vis[it]:
				self.dfs(it, vis, adj, ls)

	def dfsOfGraph(self, V, adj):
		vis = [None] * (V + 1)
		vis[0] = True
		ls = []
		self.dfs(0, vis, adj, ls)
		return ls


class Solution:

	def dfsOfGraph(self, V, adj):

		def dfs(adj, no, vis, l):
			vis[no] = 1
			l.append(no)
			for c in adj[no]:
				if vis[c] == 0:
					dfs(adj, c, vis, l)
		vis = [0] * len(adj)
		s = 0
		l = []
		dfs(adj, s, vis, l)
		return l


class Solution:

	def dfs(self, node, cache, res, adj):
		cache[node] = 1
		res.append(node)
		for neighbour in adj[node]:
			if not cache[neighbour]:
				self.dfs(neighbour, cache, res, adj)

	def dfsOfGraph(self, V, adj):
		cache = [0 for _ in range(V)]
		res = []
		self.dfs(0, cache, res, adj)
		return res


class Solution:

	def dfsOfGraph(self, V, adj):
		res = []
		visit = set()

		def dfs(node):
			visit.add(node)
			res.append(node)
			for nei in adj[node]:
				if nei not in visit:
					visit.add(nei)
					dfs(nei)
			return
		dfs(0)
		return res


class Solution:

	def dfsOfGraph(self, V, adj):
		visited = set()
		ans = []

		def DFS(x):
			visited.add(x)
			ans.append(x)
			for i in adj[x]:
				if i not in visited:
					DFS(i)
		DFS(0)
		return ans


class Solution:

	def dfs(self, currentNode, visited, adj, traversal):
		visited[currentNode] = 1
		traversal.append(currentNode)
		for neigh in adj[currentNode]:
			if visited[neigh] == 0:
				self.dfs(neigh, visited, adj, traversal)
		return

	def dfsOfGraph(self, V, adj):
		visited = [0 for j in range(V)]
		traversal = []
		self.dfs(0, visited, adj, traversal)
		return traversal


class Solution:

	def dfsOfGraph(self, V, adj):
		vis = set()
		vis.add(0)
		ans = []

		def dfs(node):
			ans.append(node)
			for ele in adj[node]:
				if ele not in vis:
					vis.add(ele)
					dfs(ele)
		dfs(0)
		return ans


class Solution:

	def _dfsnode(self, i):
		if self.visited[i]:
			return []
		dfs = []
		dfs.append(i)
		self.visited[i] = True
		for j in self.adj[i]:
			dfs += self._dfsnode(j)
		return dfs

	def dfsOfGraph(self, V, adj):
		self.visited = [False for x in range(V)]
		self.adj = adj
		return self._dfsnode(0)


class Solution:

	def dfs(self, v, visited, adj, lst):
		visited[v] = True
		lst.append(v)
		for neigh in adj[v]:
			if visited[neigh] == False:
				self.dfs(neigh, visited, adj, lst)
		return lst

	def dfsOfGraph(self, V, adj):
		visited = [False] * V
		lst = []
		lst = self.dfs(0, visited, adj, lst)
		return lst


class Solution:

	def dfsOfGraph(self, V, adj):
		visited = [0 for _ in range(V)]
		dfsList = []

		def dfsOfGraphUtil(node):
			nonlocal visited, dfsList
			visited[node] = 1
			dfsList.append(node)
			for x in adj[node]:
				if not visited[x]:
					dfsOfGraphUtil(x)
		dfsOfGraphUtil(0)
		return dfsList


class Solution:

	def dfsOfGraph(self, V, adj):
		res = []
		visited = []

		def helper(n, visited):
			visited.append(n)
			res.append(n)
			for i in adj[n]:
				if i not in visited:
					helper(i, visited)
		helper(0, visited)
		return res


class Solution:

	def dfsOfGraph(self, V, adj):
		visited = [0] * V
		result = []

		def dfs(node):
			visited[node] = 1
			result.append(node)
			for nextnode in adj[node]:
				if not visited[nextnode]:
					dfs(nextnode)
		dfs(0)
		return result


class Solution:

	def dfs(self, node, adj, visited, res):
		visited[node] = True
		res.append(node)
		for adjNode in adj[node]:
			if not visited[adjNode]:
				self.dfs(adjNode, adj, visited, res)

	def dfsOfGraph(self, V, adj):
		(res, visited) = ([], [False] * V)
		self.dfs(0, adj, visited, res)
		return res


class Solution:

	def dfsOfGraph(self, V, adj):
		visited = [False] * V
		result = []
		return self.Helper(adj, visited, result, V, 0)

	def Helper(self, adj, visited, result, V, index):
		if visited[index] == False:
			visited[index] = True
			result.append(index)
			for i in adj[index]:
				if visited[i] == False:
					self.Helper(adj, visited, result, V, i)
		return result


class Solution:

	def dfsOfGraph(self, V, adj):
		vis = [0] * V
		dfs = []

		def depth(node, dfs, adj, V):
			vis[node] = 1
			dfs.append(node)
			for i in adj[node]:
				if not vis[i]:
					depth(i, dfs, adj, V)
		depth(0, dfs, adj, V)
		return dfs


class Solution:

	def df_recursive(self, ans, visited, node, adj):
		if node in visited:
			return
		visited.add(node)
		ans.append(node)
		for nei in adj[node]:
			self.df_recursive(ans, visited, nei, adj)

	def dfsOfGraph(self, V, adj):
		visited = set()
		ans = []
		self.df_recursive(ans, visited, 0, adj)
		return ans