Given an undirected graph with V vertices and E edges, check whether it contains any cycle or not. Graph is in the form of adjacency list where adj[i] contains all the nodes ith node is having edge with.
Example 1:
Input:  
V = 5, E = 5
adj = {{1}, {0, 2, 4}, {1, 3}, {2, 4}, {1, 3}} 
Output: 1
Explanation: 
1->2->3->4->1 is a cycle.
Example 2:
Input: 
V = 4, E = 2
adj = {{}, {2}, {1, 3}, {2}}
Output: 0
Explanation: 
No cycle in the graph.
 
Your Task:
You don't need to read or print anything. Your task is to complete the function isCycle() which takes V denoting the number of vertices and adjacency list as input parameters and returns a boolean value denoting if the undirected graph contains any cycle or not, return 1 if a cycle is present else return 0.
NOTE: The adjacency list denotes the edges of the graph where edges[i] stores all other vertices to which ith vertex is connected.
 
Expected Time Complexity: O(V + E)
Expected Space Complexity: O(V)
 
Constraints:
1 ≤ V, E ≤ 10^{5}

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Spanning trees

Graph algorithms

Data structures

Graph traversal

Starter code: from typing import List

class Solution:

    #Function to detect cycle in an undirected graph.

	def isCycle(self, V: int, adj: List[List[int]]) -> bool:

		#Code here

Solutions:
from typing import List

class Solution:

	def isCyclicHelper(self, si, adj, visited, parent):
		visited[si] = True
		for i in adj[si]:
			if visited[i] is False:
				if self.isCyclicHelper(i, adj, visited, si):
					return True
			elif visited[i] is True and i != parent:
				return True
		return False

	def isCycle(self, V: int, adj: List[List[int]]) -> bool:
		visited = [False for i in range(V)]
		for node in range(V):
			if visited[node] is False:
				if self.isCyclicHelper(node, adj, visited, 0):
					return True
		return False


from typing import List

def cycle(adj, i, visited):
	parent = {0: -1}
	q = [i]
	while q:
		a = q.pop(0)
		visited.add(a)
		for i in adj[a]:
			if i in visited and i != parent[a]:
				return True
			elif i not in visited:
				q.append(i)
				parent[i] = a
				visited.add(i)
	return False

class Solution:

	def isCycle(self, V: int, adj: List[List[int]]) -> bool:
		visited = set()
		for i in range(V):
			if i not in visited:
				if cycle(adj, i, visited):
					return True
		return False


from typing import List

class Solution:

	def recur(self, ind, par, adj, vis):
		vis[ind] = 1
		for i in adj[ind]:
			if vis[i] == 0:
				if self.recur(i, ind, adj, vis):
					return True
			elif par != i:
				return True
		return False

	def isCycle(self, V: int, adj: List[List[int]]) -> bool:
		vis = [0 for i in range(V)]
		for ele in range(V):
			if vis[ele] == 0:
				vis[ele] = 1
				if self.recur(ele, -1, adj, vis):
					return True
		return False


from typing import List

class Solution:

	def isCycle(self, V: int, adj: List[List[int]]) -> bool:

		def dfs(node, parent, visited, adj):
			visited[node] = 1
			for i in adj[node]:
				if visited[i] != 1:
					if dfs(i, node, visited, adj) == True:
						return True
				elif i != parent:
					return True
			return False
		visited = [0] * V
		for i in range(V):
			if visited[i] != 1:
				if dfs(i, -1, visited, adj) == True:
					return True
		return False


from typing import List

class Solution:

	def isCycle(self, V: int, adj: List[List[int]]) -> bool:

		def bfs(src, adj, visited):
			visited[src] = 1
			q = []
			q.append([src, -1])
			while q:
				node = q[0][0]
				parent = q[0][1]
				q.pop(0)
				for i in adj[node]:
					if visited[i] != 1:
						visited[i] = 1
						q.append([i, node])
					elif parent != i:
						return True
		visited = [0] * V
		for i in range(V):
			if visited[i] != 1:
				if bfs(i, adj, visited) == True:
					return True
		return False


from typing import List
import collections

class Solution:

	def isCycle(self, V: int, adj: List[List[int]]) -> bool:
		vis = [0] * V

		def dfs(parent, node):
			q = collections.deque()
			q.append((parent, node))
			vis[node] = 1
			while q:
				(p, c) = q.pop()
				for n in adj[c]:
					if vis[n] != 1:
						vis[n] = 1
						q.append((c, n))
					elif n != p:
						return True
			return False
		for i in range(V):
			if vis[i] == 0:
				if dfs(-1, i) == True:
					return 1
		return 0


from typing import List

class Solution:

	def isCycle(self, V: int, adj: List[List[int]]) -> bool:
		visited = set()
		for node in range(V):
			if node not in visited:
				if self.dfs(adj, visited, node, -1):
					return True
		return False

	def dfs(self, adj, visited, curr, parent):
		if curr not in visited:
			visited.add(curr)
			for node in adj[curr]:
				if parent != node:
					if self.dfs(adj, visited, node, curr):
						return True
			return False
		return True


from typing import List

class Solution:

	def isCycle(self, V: int, adj: List[List[int]]) -> bool:

		def checkCycle(node, queue, visited):
			while queue:
				(n, p) = queue.pop(0)
				for adjnode in adj[n]:
					if adjnode not in visited:
						queue.append((adjnode, n))
						visited.append(adjnode)
					elif adjnode != p:
						return True
			return False

		def checkCycleDFS(node, parent, visited):
			visited.append(node)
			for adjnode in adj[node]:
				if adjnode not in visited:
					if checkCycleDFS(adjnode, node, visited):
						return True
				elif parent != -1 and adjnode != parent:
					return True
			return False
		visited = []
		for node in range(V):
			if node not in visited:
				if checkCycleDFS(node, -1, visited):
					return True
		return False


from typing import List

class Solution:

	def dfs(self, v, adj, visited, parent):
		visited[v] = True
		for neighbour in adj[v]:
			if not visited[neighbour]:
				if self.dfs(neighbour, adj, visited, v):
					return True
			elif parent != neighbour:
				return True
		return False

	def isCycle(self, V: int, adj: List[List[int]]) -> bool:
		visited = [False] * V
		for i in range(V):
			if not visited[i]:
				if self.dfs(i, adj, visited, -1):
					return True
		return False


from typing import List

class Solution:

	def util(self, adj, s, p, vis):
		vis[s] = 1
		for i in adj[s]:
			if vis[i] == 1 and i != p:
				return 1
			if vis[i] != 1:
				if self.util(adj, i, s, vis) == 1:
					return 1
		return 0

	def isCycle(self, V: int, adj: List[List[int]]) -> bool:
		vis = [0 for i in range(V)]
		for i in range(V):
			if vis[i] != 1:
				if self.util(adj, i, -1, vis) == 1:
					return 1
		return 0


from typing import List

class Solution:

	def isCycle(self, V: int, adj: List[List[int]]) -> bool:
		visited = [0] * V
		from collections import deque
		q = deque()

		def check_cycle(src, adj):
			visited[src] = 1
			q.append((src, -1))
			while q:
				(node, parent) = q.popleft()
				for neighbour in adj[node]:
					if visited[neighbour] == 0:
						visited[neighbour] = 1
						q.append((neighbour, node))
					elif neighbour != parent:
						return True
			return False
		for i in range(0, V):
			if visited[i] == 0:
				if check_cycle(i, adj):
					return True
		return False


from typing import List

class Solution:

	def isCycle(self, V: int, adj: List[List[int]]) -> bool:
		visited = set()

		def dfs(node, parent):
			visited.add(node)
			for child in adj[node]:
				if child not in visited:
					if dfs(child, node):
						return True
				elif child != parent:
					return True
			return False
		for i in range(v):
			if i not in visited:
				if dfs(i, None):
					return True
		return False


from typing import List
from collections import defaultdict

class Solution:

	def isCycle(self, V: int, adj: List[List[int]]) -> bool:
		graph = defaultdict(list)
		vis = set()
		for i in range(V):
			graph[i] = adj[i]

		def dfs(node, parent):
			if node in vis:
				return False
			vis.add(node)
			val = True
			for neigh in graph[node]:
				if neigh != parent:
					val = val and dfs(neigh, node)
			return val
		ans = True
		for key in graph.keys():
			if key not in vis:
				ans = ans and dfs(key, -1)
		return not ans


from typing import List
from collections import *

class Solution:

	def isCycle(self, V: int, adj: List[List[int]]) -> bool:

		def dfs(source):
			visited.add(source[0])
			for neghibour in adj[source[0]]:
				if neghibour not in visited:
					return dfs((neghibour, source[0]))
				elif neghibour in visited:
					if neghibour != source[1]:
						return True
			return False
		temp = False
		for i in range(V):
			visited = set()
			if i not in visited:
				temp = dfs((i, None))
				if temp:
					return temp
		return temp


from typing import List
from collections import deque

class Solution:

	def isCycle(self, V: int, adj: List[List[int]]) -> bool:
		v = len(adj)
		incoming = [0 for i in range(v)]
		for i in range(v):
			incoming[i] = len(adj[i])
		count = 0
		q = deque()
		for i in range(v):
			if incoming[i] == 1 or incoming[i] == 0:
				q.append(i)
		while q:
			count += 1
			vertex = q.popleft()
			for adjvertex in adj[vertex]:
				incoming[adjvertex] -= 1
				if incoming[adjvertex] == 1:
					incoming[adjvertex] = -1
					q.append(adjvertex)
		if count == v:
			return 0
		return 1


from typing import List
from collections import *

class Solution:

	def isCycle(self, V: int, adj: List[List[int]]) -> bool:
		visited = set()
		isCycle = False
		for i in range(V):
			if i not in visited:
				queue = deque([(i, None)])
				visited.add(i)
				while queue:
					(node, parent) = queue.popleft()
					for neghibour in adj[node]:
						if neghibour not in visited:
							queue.append((neghibour, node))
							visited.add(neghibour)
						elif neghibour in visited:
							if neghibour != parent:
								isCycle = True
								break
		return isCycle


from typing import List

class Solution:

	def isCycle(self, V: int, adj: List[List[int]]) -> bool:
		return isCyclic(adj)

def isCyclic(G):

	def visit(G, visited, parent, u):
		visited[u] = True
		for v in G[u]:
			if not visited[v]:
				parent[v] = u
				if visit(G, visited, parent, v):
					return True
			elif parent[u] != v:
				return True
		return False
	visited = [False] * len(G)
	parent = [None] * len(G)
	for u in range(len(G)):
		if not visited[u]:
			if visit(G, visited, parent, u):
				return True
	return False


from typing import List
from collections import defaultdict

class Solution:

	def isCycle(self, V: int, adj: List[List[int]]) -> bool:
		visited = set()

		def dfs(node, parent):
			visited.add(node)
			for neighbor in adj[node]:
				if neighbor not in visited:
					if dfs(neighbor, node):
						return True
				elif neighbor != parent:
					return True
		for node in range(len(adj)):
			if node not in visited:
				if dfs(node, None):
					return True
		return False


from typing import List

class Solution:

	def isCycle(self, V: int, adj: List[List[int]]) -> bool:
		color = [0] * V

		def dfs(node, parent):
			if color[node] == 2:
				return True
			if color[node] == 0:
				color[node] = 1
				for li in adj[node]:
					if li != parent:
						if not dfs(li, node):
							return False
				color[node] = 2
				return True
			return False
		for i in range(V):
			if color[i] == 0:
				if not dfs(i, None):
					return 1
		return 0


from typing import List

class Solution:

	def f(self, sv, visited, parent, adj):
		visited[sv] = True
		for i in range(len(adj[sv])):
			if visited[adj[sv][i]] == False:
				if self.f(adj[sv][i], visited, sv, adj) == True:
					return True
			elif parent != adj[sv][i]:
				return True
		return False

	def isCycle(self, V: int, adj: List[List[int]]) -> bool:
		visited = [False] * V
		for i in range(V):
			if visited[i] == False:
				if self.f(i, visited, -1, adj) == True:
					return True
		return False


from typing import List
from collections import deque

class Solution:

	def detect(self, node, parent, adj, vs):
		vs[node] = True
		for nbr in adj[node]:
			if vs[nbr] == False:
				if self.detect(nbr, node, adj, vs) == True:
					return True
			elif nbr != parent:
				return True
		return False

	def isCycle(self, V: int, adj: List[List[int]]) -> bool:
		vs = [False for _ in range(V)]
		for i in range(V):
			if vs[i] == False:
				if self.detect(i, -1, adj, vs) == True:
					return True
		return False


from typing import List
from collections import deque

class Solution:

	def detect(self, q, vs):
		while len(q) > 0:
			rp = q.popleft()
			node = rp[0]
			parent = rp[1]
			for nbr in adj[node]:
				if vs[nbr] == False:
					q.append((nbr, node))
					vs[nbr] = True
				elif nbr != parent:
					return True
		return False

	def isCycle(self, V: int, adj: List[List[int]]) -> bool:
		q = deque()
		vs = [False for _ in range(V)]
		for i in range(V):
			if vs[i] == False:
				q.append((i, -1))
				vs[i] = True
				if self.detect(q, vs) == True:
					return True
		return False


from typing import List
from collections import deque

class Solution:

	def isCycle(self, V: int, adj: List[List[int]]) -> bool:
		visited = set()

		def isCycle_dfs(node, parent):
			visited.add(node)
			for nei in adj[node]:
				if nei not in visited:
					visited.add(nei)
					if isCycle_dfs(nei, node):
						return True
				elif nei != parent:
					return True
			return False
		for node in range(V):
			if node not in visited:
				if isCycle_dfs(node, -1):
					return True
		return False


from typing import List
from collections import deque

class Solution:

	def isCycle(self, V: int, adj: List[List[int]]) -> bool:
		visited = set()

		def detectCycle_bfs(node):
			q = deque()
			q.append((node, -1))
			visited.add(node)
			while q:
				(tNode, parent) = q.popleft()
				for nei in adj[tNode]:
					if nei not in visited:
						visited.add(nei)
						q.append((nei, tNode))
					elif nei != parent:
						return True
			return False
		for node in range(V):
			if node not in visited:
				if detectCycle_bfs(node):
					return True
		return False


from typing import List

class Solution:

	def isCycle(self, V: int, adj: List[List[int]]) -> bool:
		indegree = [0] * V

		def dfs(cur, par):
			if indegree[cur] == 2:
				return False
			if indegree[cur] == 1:
				return True
			indegree[cur] = 1
			for ne in adj[cur]:
				if ne != par:
					if dfs(ne, cur):
						return True
			indegree[cur] = 2
			return False
		for i in range(V):
			if indegree[i] == 0:
				if dfs(i, -1):
					return True
		return False


from typing import List
from collections import deque

class Solution:

	def isCycle(self, V: int, adj: List[List[int]]) -> bool:
		visited = [0] * V
		for i in range(0, V):
			if visited[i] == 0:
				if self.helper(i, visited, adj) == True:
					return True
		return False

	def helper(self, source, visited, adj):
		visited[source] = 1
		queue = deque()
		queue.append([source, -1])
		while queue:
			ele = queue.popleft()
			node = ele[0]
			parent = ele[1]
			for neigh in adj[node]:
				if visited[neigh] == 0:
					queue.append([neigh, node])
					visited[neigh] = 1
				elif neigh != parent:
					return True
		return False


from typing import List

class Solution:

	def isCycle(self, V: int, adj: List[List[int]]) -> bool:
		visited = set()

		def dfs(node, parent):
			for child in adj[node]:
				if child not in visited:
					visited.add(child)
					ans = dfs(child, node)
					if ans:
						return 1
				elif child != parent:
					return 1
			return 0
		for key in range(len(adj)):
			if key not in visited:
				visited.add(key)
				val = dfs(key, -1)
				if val:
					return 1
		return 0


from typing import List
from collections import deque

class Solution:

	def isCycle(self, V: int, adj: List[List[int]]) -> bool:

		def dfs(src, adj, par, visited):
			visited[src] = 1
			for nei in adj[src]:
				if visited[nei] == 0:
					if dfs(nei, adj, src, visited):
						return True
				elif par != nei:
					return True
			return False
		visited = [0 for i in range(V)]
		for i in range(V):
			if visited[i] == 0 and dfs(i, adj, -1, visited):
				return 1
		return 0


from typing import List
from collections import deque

class Solution:

	def isCycle(self, V: int, adj: List[List[int]]) -> bool:
		inDegree = [0 for _ in range(V)]
		for edge in adj:
			for e in edge:
				inDegree[e] += 1
		queue = deque([])
		visited = set()
		for i in range(V):
			if inDegree[i] <= 1:
				queue.append(i)
				visited.add(i)
		order = []
		while queue:
			current = queue.popleft()
			order.append(current)
			visited.add(current)
			for nei in adj[current]:
				if nei not in visited:
					inDegree[nei] -= 1
					if inDegree[nei] == 1:
						queue.append(nei)
		if len(order) < V:
			return 1
		return 0


from typing import List

class Solution:

	def isCycle(self, V: int, adj: List[List[int]]) -> bool:
		vis = [False] * V
		for i in range(V):
			if not vis[i]:
				if self.checkForCycle(i, -1, vis, adj):
					return True
		return False

	def checkForCycle(self, node, parent, vis, adj):
		vis[node] = True
		for it in adj[node]:
			if not vis[it]:
				if self.checkForCycle(it, node, vis, adj):
					return True
			elif it != parent:
				return True
		return False


from typing import List

class Solution:

	def dfs(self, src, parent, vis, adj):
		vis[src] = 1
		for i in adj[src]:
			if vis[i] == 0:
				if self.dfs(i, src, vis, adj):
					return True
			elif i != parent:
				return True
		return False

	def isCycle(self, V: int, adj: List[List[int]]) -> bool:
		vis = [0 for _ in range(V)]
		for i in range(V):
			if vis[i] == 0:
				if self.dfs(i, -1, vis, adj):
					return True
		return False


from typing import List

class Solution:

	def isCycle(self, V: int, adj: List[List[int]]) -> bool:
		queue = []
		visited = [0 for i in range(V)]
		adjacency_list = adj
		parent = {}
		for i in range(len(visited)):
			if (visited[i] != 1) & (adj[i] != []):
				queue.append(i)
				visited[i] = 1
				parent[i] = -1
				while len(queue) != 0:
					k = set(adjacency_list[queue[0]])
					for j in k:
						if (visited[j] == 1) & (j not in parent):
							return 1
						elif visited[j] == 0:
							queue.append(j)
							visited[j] = 1
							parent[queue[0]] = j
					queue.pop(0)
		return 0


from collections import deque
from typing import List

class Solution:

	def isCycle(self, V: int, adj: List[List[int]]) -> bool:
		visited = set()
		queue = deque()
		for vertix in range(V):
			if vertix not in visited:
				queue.append((vertix, -1))
				visited.add(vertix)
			while queue:
				(cur, parent) = queue.popleft()
				for val in adj[cur]:
					if val in visited and val != parent:
						return True
					elif val not in visited:
						queue.append((val, cur))
						visited.add(val)
		return False


from typing import List

class Solution:

	def hasCycle(self, v, adj, color, parent):
		if color[v] == 1:
			return True
		if color[v] == 2:
			return False
		color[v] = 1
		for next_v in adj[v]:
			if next_v == parent:
				continue
			if self.hasCycle(next_v, adj, color, v):
				return True
		color[v] = 2
		return False

	def isCycle(self, V: int, adj: List[List[int]]) -> bool:
		color = [0] * V
		for i in range(V):
			if self.hasCycle(i, adj, color, -1):
				return True
		return False


from typing import List

class Solution:

	def isCycle(self, V: int, adj: List[List[int]]) -> bool:
		queue = []
		visited = [0 for i in range(V)]
		adjacency_list = adj
		for i in range(len(visited)):
			if visited[i] != 1:
				queue.append(i)
				visited[i] == 1
			while len(queue) != 0:
				k = adjacency_list[queue[0]]
				for i in k:
					if (visited[i] == 1) & (parent is not None):
						if i in parent:
							return 1
					else:
						queue.append(i)
						visited[i] = 1
				parent = adjacency_list[queue[0]]
				queue.pop(0)
		return 0
from typing import List
from typing import List

class Solution:

	def isCycle(self, V: int, adj: List[List[int]]) -> bool:
		visited = [False] * V
		parent = [-1] * V
		for v in range(V):
			if not visited[v]:
				if self.isCycleUtil(v, adj, visited, parent):
					return True
		return False

	def isCycleUtil(self, v: int, adj: List[List[int]], visited: List[bool], parent: List[int]) -> bool:
		queue = [(v, -1)]
		visited[v] = True
		while queue:
			(node, par) = queue.pop(0)
			for neighbor in adj[node]:
				if not visited[neighbor]:
					visited[neighbor] = True
					queue.append((neighbor, node))
				elif par != neighbor:
					return True
		return False


from typing import List

class Solution:

	def isCycle(self, V: int, adj: List[List[int]]) -> bool:
		visited = set()

		def dfs(node, par):
			visited.add(node)
			for neigh in adj[node]:
				if neigh != par:
					if neigh in visited:
						return 1
					if dfs(neigh, node):
						return 1
		for node in range(V):
			if node not in visited:
				if dfs(node, -1):
					return 1
		return 0


from typing import List

class Solution:

	def isCycle(self, V: int, adj: List[List[int]]) -> bool:
		from collections import deque
		for j in range(V):
			q = deque()
			vis = [False] * V
			q.append(j)
			while q:
				u = q.popleft()
				vis[u] = True
				for i in adj[u]:
					if q.count(i) == 1:
						return True
					if vis[i] == False:
						q.append(i)
		return False


from typing import List
from collections import deque
from collections import defaultdict

class Solution:

	def isCycle(self, V: int, adj: List[List[int]]) -> bool:
		visited = set()

		def dfs(node, parent):
			for neigh in adj[node]:
				if neigh != parent:
					if neigh in visited:
						return True
					else:
						visited.add(neigh)
						if dfs(neigh, node):
							return True
			return False
		for i in range(v):
			if i not in visited:
				visited.add(i)
				if dfs(i, None):
					return True
		return False


from typing import List

class Solution:

	def isCycle(self, V: int, adj: List[List[int]]) -> bool:
		visited = [0 for i in range(V)]
		for i in range(V):
			if not visited[i]:
				check = self.findCycle(i, adj, visited, -1)
				if check:
					return True
		return False

	def findCycle(self, src, adj, visited, parent):
		queue = []
		queue.append((src, -1))
		while queue:
			(node, parent) = queue.pop(0)
			visited[node] = 1
			for adjacents in adj[node]:
				if visited[adjacents] == 0:
					queue.append((adjacents, node))
				elif adjacents != parent:
					return True


from typing import List
import collections

class Solution:

	def bfs(self, adj, visited, queue, i):
		visited[i] = 1
		queue.append((i, -1))
		while queue:
			popvalue = queue.popleft()
			for i in adj[popvalue[0]]:
				if visited[i] == 0:
					visited[i] = 1
					queue.append((i, popvalue[0]))
				elif popvalue[1] != i:
					return True

	def isCycle(self, V: int, adj: List[List[int]]) -> bool:
		visited = [0] * V
		queue = collections.deque([])
		for i in range(len(adj)):
			if visited[i] != 1:
				if self.bfs(adj, visited, queue, i):
					return True
		return False


from typing import List

class Solution:

	def isCycle(self, V: int, adj: List[List[int]]) -> bool:
		parent = [i for i in range(V)]
		for u in range(V):
			for v in adj[u]:
				if u < v:
					parent_u = find(u, parent)
					parent_v = find(v, parent)
					if parent_u == parent_v:
						return True
					else:
						union(parent_u, parent_v, parent)
		return False

def find(u, parent):
	if u == parent[u]:
		return u
	return find(parent[u], parent)

def union(u, v, parent):
	u_parent = find(u, parent)
	v_parent = find(v, parent)
	if u_parent == v_parent:
		return
	else:
		parent[v_parent] = u_parent


from typing import List

class Solution:

	def isCycle(self, V: int, adj: List[List[int]]) -> bool:

		def DFS(node, visited, parent):
			visited[node] = True
			for child in adj[node]:
				if not visited[child]:
					check = DFS(child, visited, node)
					if check:
						return True
				elif child != parent:
					return True
			return False
		visited = [False] * V
		for i in range(V):
			if not visited[i]:
				check = DFS(i, visited, -1)
				if check:
					return True
		return False


from typing import List
from collections import defaultdict

class Solution:

	def isCycle(self, V: int, adj: List[List[int]]) -> bool:

		def dfs(node, parent):
			if color[node] == 2:
				return False
			if color[node] == 1:
				return True
			color[node] = 1
			for neighbour in adj[node]:
				if parent != neighbour and dfs(neighbour, node):
					return True
			color[node] = 2
			return False
		color = [0] * V
		for node in range(V):
			if dfs(node, None):
				return 1
		return 0


from typing import List
from collections import defaultdict

class Solution:

	def isCycle(self, V: int, adj: List[List[int]]) -> bool:
		visited = set()
		graph = defaultdict(list)
		parent = defaultdict(lambda : None)
		index = 0
		for node in adj:
			for neg in node:
				graph[index].append(neg)
			index += 1

		def dfs(node):
			visited.add(node)
			for neighbor in graph[node]:
				if neighbor not in visited:
					parent[neighbor] = node
					if dfs(neighbor):
						return True
				elif neighbor != parent[node]:
					return True
			return False
		for node in graph:
			if node not in visited:
				if dfs(node):
					return True
		return False


from typing import List

class Solution:

	def isCycle(self, V: int, adj: List[List[int]]) -> bool:
		graph = {}
		for (i, node) in enumerate(adj):
			graph[i] = node
		visited = set()
		for n in graph.keys():
			if n not in visited:
				ls = [(n, None)]
				while len(ls):
					(node, parent) = ls.pop(0)
					visited.add(node)
					for neighbor in graph[node]:
						if neighbor not in visited:
							ls.append((neighbor, node))
						elif neighbor != parent:
							return True
		return False