Given a Directed Graph with V vertices (Numbered from 0 to V-1) and E edges, check whether it contains any cycle or not.
Example 1:
Input:
Output: 1
Explanation: 3 -> 3 is a cycle
Example 2:
Input:
Output: 0
Explanation: no cycle in the graph
Your task:
You dont need to read input or print anything. Your task is to complete the function isCyclic() which takes the integer V denoting the number of vertices and adjacency list adj as input parameters and returns a boolean value denoting if the given directed graph contains a cycle or not.
In the adjacency list adj, element adj[i][j] represents an edge from i to j.
Expected Time Complexity: O(V + E)
Expected Auxiliary Space: O(V)
Constraints:
1 ≤ V, E ≤ 10^{5}

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Graph algorithms

Data structures

Starter code: #User function Template for python3





class Solution:

    

    #Function to detect cycle in a directed graph.

    def isCyclic(self, V, adj):

        # code here

Solutions:
def dfs_cycle(adj, a, visited, dfs_call):
	if a in visited and a in dfs_call:
		return True
	elif a not in visited:
		visited.add(a)
		dfs_call.add(a)
		for i in adj[a]:
			if dfs_cycle(adj, i, visited, dfs_call):
				return True
		dfs_call.remove(a)
		return False

class Solution:

	def isCyclic(self, V, adj):
		visited = set()
		dfs_call = set()
		for a in range(V):
			if a not in visited:
				if dfs_cycle(adj, a, visited, dfs_call):
					return True
		return False


from collections import deque

class Solution:

	def isCyclic(self, V, adj):
		ind = [0 for i in range(V)]
		for i in range(V):
			for j in adj[i]:
				ind[j] += 1
		q = deque()
		for i in range(V):
			if ind[i] == 0:
				q.append(i)
		count = 0
		while len(q) > 0:
			node = q.popleft()
			count += 1
			for nei in adj[node]:
				ind[nei] -= 1
				if ind[nei] == 0:
					q.append(nei)
		return count != V


class Solution:

	def __isCyclicHelper(self, si, adj, visited, stack):
		visited[si] = True
		stack[si] = True
		for i in adj[si]:
			if visited[i] is False:
				if self.__isCyclicHelper(i, adj, visited, stack):
					return True
			elif stack[i] == True:
				return True
		stack[si] = False
		return False

	def isCyclic(self, V, adj):
		visited = [False for i in range(V)]
		stack = [False for i in range(V)]
		for node in range(V):
			if visited[node] is False:
				if self.__isCyclicHelper(node, adj, visited, stack):
					return True
		return False


class Solution:

	def isCyclic(self, V, adj):
		indegree = [0 for _ in range(V)]
		for x in range(len(adj)):
			for i in adj[x]:
				indegree[i] += 1
		queue = []
		for i in range(V):
			if indegree[i] == 0:
				queue.append(i)
		cnt = 0
		while len(queue) != 0:
			temp = queue.pop(0)
			cnt += 1
			for x in adj[temp]:
				indegree[x] -= 1
				if indegree[x] == 0:
					queue.append(x)
		return cnt != V


class Solution:

	def isCyclic(self, v, adj):
		ind = [0] * (v + 1)
		count = 0
		for i in adj:
			for j in i:
				ind[j] += 1
		(q, ans) = ([], [])
		for i in range(v):
			if ind[i] == 0:
				q.append(i)
		while len(q) > 0:
			u = q.pop(0)
			count += 1
			ans.append(u)
			for i in adj[u]:
				ind[i] -= 1
				if ind[i] == 0:
					q.append(i)
		if count < v:
			return 1
		return 0


class Solution:

	def isCyclic(self, V, lst):

		def dfs(s, visited, stack):
			visited[s] = 1
			stack[s] = 1
			for nbr in lst[s]:
				if stack[nbr]:
					return 1
				elif visited[nbr] == 0:
					cycle = dfs(nbr, visited, stack)
					if cycle:
						return 1
			stack[s] = 0
			return 0

		def cycleDetection(v):
			visited = [0] * v
			stack = [0] * v
			for i in range(v):
				if visited[i] == 0:
					if dfs(i, visited, stack):
						return 1
			return 0
		return cycleDetection(V)


from collections import deque

class Solution:

	def dfs(self, node, V, adj, visited, pathvisited):
		visited[node] = True
		pathvisited[node] = True
		for i in adj[node]:
			if not visited[i]:
				if self.dfs(i, V, adj, visited, pathvisited):
					return True
			elif pathvisited[i]:
				return True
		pathvisited[node] = False
		return False

	def isCyclic(self, V, adj):
		visited = [False] * V
		pathvisited = [False] * V
		for i in range(V):
			if not visited[i]:
				if self.dfs(i, V, adj, visited, pathvisited):
					return True
		return False


class Solution:

	def isCyclic(self, v, adj):
		visited = [False] * (v + 1)
		rec = [False] * (v + 1)
		for i in range(v):
			if visited[i] == False:
				if self.dfsRec(adj, i, visited, rec) == True:
					return True
		return False

	def dfsRec(self, arr, s, visited, rec):
		visited[s] = True
		rec[s] = True
		for i in arr[s]:
			if visited[i] == False and self.dfsRec(arr, i, visited, rec):
				return True
			if visited[i] and rec[i]:
				return True
		rec[s] = False
		return False


class Solution:

	def isCyclic(self, V, adj):
		pathVisited = [None] * V

		def dfs(node):
			pathVisited[node] = 2
			for nei in adj[node]:
				if pathVisited[nei] == None:
					if dfs(nei):
						return True
				elif pathVisited[nei] == 2:
					return True
			pathVisited[node] -= 1
			return False
		for i in range(V):
			if pathVisited[i] == None:
				if dfs(i):
					return True
		return False


class Solution:

	def isCyclic(self, V, adj):
		visited = set()
		pathVisited = [None] * V

		def dfs(node):
			visited.add(node)
			pathVisited[node] = 1
			for nei in adj[node]:
				if nei not in visited:
					if dfs(nei):
						return True
				elif pathVisited[nei] == 1:
					return True
			pathVisited[node] = 0
			return False
		for i in range(V):
			if i not in visited:
				if dfs(i):
					return True
		return False


class Solution:

	def isCyclic(self, V, adj):
		indegree = [0 for i in range(V)]
		for i in range(V):
			for child in adj[i]:
				indegree[child] += 1
		queue = []
		for i in range(0, len(indegree)):
			if indegree[i] == 0:
				queue.append(i)
		count = 0
		while queue:
			node = queue.pop(0)
			count += 1
			for child in adj[node]:
				indegree[child] = indegree[child] - 1
				if indegree[child] == 0:
					queue.append(child)
		if count != V:
			return 1
		return 0


class Solution:

	def isCyclic(self, V, adj):
		visited = set()
		safe = set()
		for node in range(V):
			if node not in visited:
				if self.dfs(node, -1, adj, visited, safe) is True:
					return True
		return False

	def dfs(self, node, parent, adj, visited, safe):
		if node not in visited:
			visited.add(node)
			for child in adj[node]:
				if self.dfs(child, node, adj, visited, safe) is True:
					return True
			safe.add(node)
			return False
		elif node in safe:
			return False
		return True


class Solution:

	def isCyclic(self, V, adj):
		return is_directed_graph_cyclic(adj)

def is_directed_graph_cyclic(G):

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


class Solution:

	def isCyclic(self, v, adjList):

		def dfs(i, adjList, vis, vis_dfs):
			vis[i] = 1
			vis_dfs[i] = 1
			for j in adjList[i]:
				if vis[j] == 0:
					if dfs(j, adjList, vis, vis_dfs):
						return True
				elif vis_dfs[j] == 1:
					return True
			vis_dfs[i] = 0

		def checkCycle(v, adjList):
			vis = []
			vis_dfs = []
			for i in range(v):
				vis.append(0)
				vis_dfs.append(0)
			for i in range(v):
				if vis[i] == 0:
					if dfs(i, adjList, vis, vis_dfs):
						return True
			return False
		return checkCycle(v, adjList)


class Solution:

	def isCyclic(self, V, adj):
		visited = [0 for i in range(V)]

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


class Solution:

	def isCyclic(self, V, adj):
		indegree = [0] * V
		for i in range(V):
			for j in adj[i]:
				indegree[j] += 1
		queue = []
		for i in range(V):
			if indegree[i] == 0:
				queue.append(i)
		ans = []
		while queue:
			a = queue.pop(0)
			ans.append(a)
			for i in adj[a]:
				indegree[i] -= 1
				if indegree[i] == 0:
					queue.append(i)
		if len(ans) == V:
			return 0
		else:
			return 1


class Solution:

	def isCyclic(self, V, adj):
		indegree = [0] * V
		queue = []
		stack = []
		for i in range(V):
			for j in adj[i]:
				indegree[j] += 1
		for i in range(V):
			if indegree[i] == 0:
				queue.append(i)
		while queue:
			x = queue.pop(0)
			stack.append(x)
			for i in adj[x]:
				indegree[i] -= 1
				if indegree[i] == 0:
					queue.append(i)
		if len(stack) == V:
			return False
		return True


class Solution:

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

	def isCyclic(self, V, adj):
		vis = [0] * V
		dvis = [0] * V
		for i in range(V):
			if vis[i] == 0:
				if self.dfs(i, vis, dvis, adj):
					return True
		return False


class Solution:

	def dfs(self, idx, adj, visited, pathVisited):
		visited[idx] = 1
		pathVisited[idx] = 1
		for j in adj[idx]:
			if not visited[j]:
				if self.dfs(j, adj, visited, pathVisited):
					return True
			elif pathVisited[j]:
				return True
		pathVisited[idx] = 0
		return False

	def isCyclic(self, V, adj):
		visited = [0 for i in range(V)]
		pathVisited = [0 for i in range(V)]
		for (idx, i) in enumerate(adj):
			if not visited[idx]:
				if self.dfs(idx, adj, visited, pathVisited):
					return True
		return False


class Solution:

	def isCyclic(self, V, adj):

		def detect(adj, s, visited, rect):
			visited[s] = True
			rect[s] = True
			for i in adj[s]:
				if visited[i] == False:
					if detect(adj, i, visited, rect):
						return 1
				elif rect[i] == True:
					return 1
			rect[s] = False
			return 0
		visited = [False] * len(adj)
		rect = [False] * len(adj)
		for i in range(len(adj)):
			if visited[i] == False:
				if detect(adj, i, visited, rect):
					return 1
		return 0


class Solution:

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

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


from collections import defaultdict

class Solution:
	visited = {}
	adjl = []
	recStack = []

	def dfs(self, node):
		Solution.visited[node] = True
		Solution.recStack[node] = True
		for i in Solution.adjl[node]:
			if not Solution.visited[i]:
				if self.dfs(i):
					return True
			elif Solution.recStack[i]:
				return True
		Solution.recStack[node] = False
		return False

	def isCyclic(self, V, adj):
		Solution.visited = defaultdict(bool)
		Solution.adjl = adj
		Solution.recStack = defaultdict(bool)
		for i in range(V):
			if not Solution.visited[i]:
				if self.dfs(i):
					return True
		return False


class Solution:

	def isCyclic(self, V, adj):

		def dfsOfGraphUtil(node):
			visited[node] = 1
			pathVisited[node] = 1
			for x in adj[node]:
				if not visited[x]:
					if dfsOfGraphUtil(x):
						return 1
				elif visited[x] and pathVisited[x]:
					return 1
			pathVisited[node] = 0
			return 0
		visited = [0 for _ in range(V)]
		pathVisited = [0 for _ in range(V)]
		for i in range(V):
			if not visited[i]:
				if dfsOfGraphUtil(i):
					return 1
		return 0


class Solution:

	def isCyclic(self, V, adj):
		visited = [False] * V
		helper = [False] * V
		for i in range(0, V):
			if visited[i] == False:
				ans = self.dfs(i, visited, helper)
				if ans == True:
					return True
		return False

	def dfs(self, i, visited, helper):
		visited[i] = True
		helper[i] = True
		for neighbour in adj[i]:
			if helper[neighbour] == True:
				return True
			if visited[neighbour] == False:
				ans = self.dfs(neighbour, visited, helper)
				if ans == True:
					return True
		helper[i] = False
		return False


class Solution:

	def isCyclic(self, V, adj):
		visited = [False] * V
		helper = [False] * V
		for i in range(0, V):
			if visited[i] == False:
				ans = self.dfs(i, visited, helper)
				if ans == True:
					return True
		return False

	def dfs(self, i, visited, helper):
		visited[i] = True
		helper[i] = True
		neighbours = adj[i]
		for k in range(len(neighbours)):
			curr = neighbours[k]
			if helper[curr] == True:
				return True
			if visited[curr] == False:
				ans = self.dfs(curr, visited, helper)
				if ans == True:
					return True
		helper[i] = False
		return False


class Solution:

	def dfsCheck(self, node, vis, pathVis, adj):
		vis[node] = True
		pathVis[node] = True
		for nei in adj[node]:
			if vis[nei] == False:
				if self.dfsCheck(nei, vis, pathVis, adj) == True:
					return True
			elif pathVis[nei] == True:
				return True
		pathVis[node] = False
		return False

	def isCyclic(self, V, adj):
		vis = [False for i in range(V)]
		pathVis = [False for i in range(V)]
		for i in range(V):
			if vis[i] == False:
				if self.dfsCheck(i, vis, pathVis, adj) == True:
					return True
		return False


from collections import deque

class Solution:

	def isCyclic(self, V, adj):
		indegree = [0] * V
		que = deque()
		for node in range(V):
			for adjNode in adj[node]:
				indegree[adjNode] += 1
		for (index, value) in enumerate(indegree):
			if value == 0:
				que.append(index)
		count = 0
		while que:
			node = que.popleft()
			count += 1
			for adjNode in adj[node]:
				indegree[adjNode] -= 1
				if indegree[adjNode] == 0:
					que.append(adjNode)
		if count == V:
			return 0
		else:
			return 1


class Solution:

	def isCyclic(self, V, adj):
		visited = [False] * V
		recursionStack = [False] * V

		def dfs(vertex):
			visited[vertex] = True
			recursionStack[vertex] = True
			for neighbor in adj[vertex]:
				if recursionStack[neighbor]:
					return True
				elif not visited[neighbor]:
					if dfs(neighbor):
						return True
			recursionStack[vertex] = False
			return False
		for i in range(V):
			if not visited[i]:
				if dfs(i):
					return True
		return False


from collections import deque

class Solution:

	def isCyclic(self, V, adj):
		indegree = [0] * V
		for i in range(V):
			for adj_node in adj[i]:
				indegree[adj_node] += 1
		q = deque()
		for i in range(len(indegree)):
			if indegree[i] == 0:
				q.append(i)
		final = []
		while q:
			z = q.popleft()
			final.append(z)
			for adj_node in adj[z]:
				indegree[adj_node] -= 1
				if indegree[adj_node] == 0:
					q.append(adj_node)
		return len(final) != V


import collections

class Solution:

	def isCyclic(self, V, adj):

		def detectCycle(node, adj, vis, dvis):
			vis[node] = 1
			dvis[node] = 1
			for adj_node in adj[node]:
				if vis[adj_node] == 1 and dvis[adj_node] == 1:
					return True
				elif vis[adj_node] == -1:
					vis[adj_node] = 1
					dvis[adj_node] = 1
					if detectCycle(adj_node, adj, vis, dvis):
						return True
			dvis[node] = 0
		vis = [-1] * V
		dvis = [-1] * V
		for i in range(V):
			if vis[i] == -1:
				if detectCycle(i, adj, vis, dvis):
					return True
		return False


class Solution:

	def isCyclic(self, V, adj):
		visit = [False] * V
		dfsvisit = [False] * V

		def dfs(visit, dfsvisit, node):
			visit[node] = True
			dfsvisit[node] = True
			for x in adj[node]:
				if not visit[x]:
					if dfs(visit, dfsvisit, x):
						return True
				elif dfsvisit[x]:
					return True
			dfsvisit[node] = False
			return False
		for i in range(V):
			if not visit[i]:
				if dfs(visit, dfsvisit, i):
					return 1
		return 0


def iscycle(node, adj):
	if dfsvis[node] == 1:
		return True
	elif vis[node] == 1:
		return
	else:
		vis[node] = 1
		dfsvis[node] = 1
		for i in adj[node]:
			if iscycle(i, adj):
				return True
		dfsvis[node] = 0
		return False

class Solution:

	def isCyclic(self, V, adj):
		global vis
		global dfsvis
		vis = []
		dfsvis = []
		for i in range(V):
			vis.append(0)
			dfsvis.append(0)
		for i in range(V):
			if vis[i] == 0:
				if iscycle(i, adj) == True:
					return True
		return False


class Solution:

	def isCyclic(self, V, adj):
		visited = set()
		stack_tracker = [False] * V

		def dfs(node):
			visited.add(node)
			stack_tracker[node] = True
			for nei in adj[node]:
				if nei not in visited:
					if dfs(nei):
						return True
				elif stack_tracker[nei]:
					return True
			stack_tracker[node] = False
			return False
		for i in range(V):
			if i not in visited:
				if dfs(i):
					return True
		return False


class Solution:

	def isCyclic(self, V, adj):
		recs = [False for i in range(V)]
		visited = [False for i in range(V)]
		for i in range(V):
			if not visited[i]:
				if self.do_dfs(recs, visited, i, adj):
					return True
		return False

	def do_dfs(self, resc, visited, v, adj):
		resc[v] = True
		visited[v] = True
		for n in adj[v]:
			if not visited[n]:
				if self.do_dfs(resc, visited, n, adj):
					return True
			elif resc[n]:
				return True
		resc[v] = False
		return False


class Solution:

	def isCyclic(self, V, adj):
		colors = [0] * V

		def hasCycle(node):
			if colors[node] == 1:
				return True
			if colors[node] == 2:
				return False
			colors[node] = 1
			for neigh in adj[node]:
				if hasCycle(neigh):
					return True
			colors[node] = 2
			return False
		for node in range(V):
			if colors[node] == 0:
				if hasCycle(node):
					return True
		return False


class Solution:

	def isCyclicUtil(self, v, visited, recStack, adj):
		visited[v] = True
		recStack[v] = True
		for neighbor in adj[v]:
			if not visited[neighbor]:
				if self.isCyclicUtil(neighbor, visited, recStack, adj):
					return True
			elif recStack[neighbor]:
				return True
		recStack[v] = False
		return False

	def isCyclic(self, V, adj):
		visited = [False] * V
		recStack = [False] * V
		for v in range(V):
			if not visited[v]:
				if self.isCyclicUtil(v, visited, recStack, adj):
					return True
		return False


class Solution:

	def isCyclic(self, V, adj):
		visited = [0] * V
		pathvisited = [0] * V

		def DFS(node):
			visited[node] = 1
			pathvisited[node] = 1
			for i in adj[node]:
				if visited[i] == False:
					if DFS(i):
						return True
				elif pathvisited[i]:
					return True
			pathvisited[node] = 0
			return False
		for i in range(V):
			if visited[i] == 0:
				if DFS(i) == True:
					return True
		return False


from collections import deque

class Solution:

	def isCyclic(self, V, adj):
		indegree = [0] * V
		for i in range(V):
			for it in adj[i]:
				indegree[it] += 1
		q = deque()
		for i in range(V):
			if indegree[i] == 0:
				q.append(i)
		cnt = 0
		while q:
			node = q.popleft()
			cnt += 1
			for it in adj[node]:
				indegree[it] -= 1
				if indegree[it] == 0:
					q.append(it)
		if cnt == V:
			return False
		return True


from typing import List

class Solution:

	def dfsCheck(self, node: int, adj: List[List[int]], vis: List[int], pathVis: List[int]) -> bool:
		(vis[node], pathVis[node]) = (1, 1)
		for it in adj[node]:
			if vis[it] == 0:
				if self.dfsCheck(it, adj, vis, pathVis):
					return True
			elif pathVis[it] == 1:
				return True
		pathVis[node] = 0
		return False

	def isCyclic(self, V, adj):
		vis = [0] * V
		pathVis = [0] * V
		for i in range(V):
			if vis[i] == 0:
				if self.dfsCheck(i, adj, vis, pathVis):
					return True
		return False


class Solution:

	def isCyclic(self, V, adj):
		path = set()
		v = set()

		def dfs(node):
			path.add(node)
			v.add(node)
			for x in adj[node]:
				if x not in v:
					if dfs(x):
						return True
				elif x in path:
					return True
			path.remove(node)
			return False
		for x in range(V):
			if x not in v:
				if dfs(x):
					return True
		return False


class Solution:

	def isCyclic(self, V, adj):
		path = [0] * V
		visited = [0] * V

		def traverse(node, adj, visited, path):
			visited[node] = 1
			path[node] = 1
			for i in adj[node]:
				if visited[i] == 1 and path[i] == 1:
					return 1
				if visited[i] == 0:
					if traverse(i, adj, visited, path):
						return 1
			path[node] = 0
		for i in range(V):
			if visited[i] == 0:
				if traverse(i, adj, visited, path):
					return 1
		return 0


class Solution:

	def isCyclic(self, V, adj):

		def dfs(node):
			visited[node] = 1
			path_visited[node] = 1
			for i in adj[node]:
				if visited[i] == 0:
					if dfs(i) == True:
						return True
				elif path_visited[i] == 1:
					return True
			path_visited[node] = 0
			return False
		visited = [0 for i in range(V)]
		path_visited = [0 for i in range(V)]
		for i in range(V):
			if visited[i] == 0:
				if dfs(i) == True:
					return 1
		return 0


class Solution:

	def isCyclic(self, V, adj):
		visited = [False for i in range(V)]
		inRecurison = [False for i in range(V)]
		for i in range(V):
			if visited[i] == False:
				if isCyclicDFS(i, adj, visited, inRecurison) == True:
					return True
		return False

def isCyclicDFS(sv, adj, visited, inRecurison):
	visited[sv] = True
	inRecurison[sv] = True
	for i in adj[sv]:
		if inRecurison[i] == True and visited[i] == True:
			return True
		if visited[i] == False:
			if isCyclicDFS(i, adj, visited, inRecurison) == True:
				return True
	inRecurison[sv] = False
	return False


from collections import deque

class Solution:

	def isCyclic(self, V, adj):
		indegree = [0] * V
		for node in range(V):
			for vertice in adj[node]:
				indegree[vertice] += 1
		q = deque()
		for node in range(V):
			if indegree[node] == 0:
				q.append(node)
		count = 0
		while q:
			node = q.popleft()
			count += 1
			for vertice in adj[node]:
				indegree[vertice] -= 1
				if indegree[vertice] == 0:
					q.append(vertice)
		return False if count == V else True


from collections import deque

class Solution:

	def isCyclic(self, V, adj):
		degree = [0 for x in range(V)]
		for x in range(V):
			for i in adj[x]:
				degree[i] += 1
		d = deque()
		for (x, y) in enumerate(degree):
			if y == 0:
				d.append(x)
		curr = 0
		while d:
			node = d.popleft()
			curr += 1
			for x in adj[node]:
				degree[x] -= 1
				if degree[x] == 0:
					d.append(x)
		return curr != V


class Solution:

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

		def dfs(node, graph, visited, recr):
			visited[node] = True
			recr[node] = True
			for neighbor in graph[node]:
				if visited[neighbor] == False:
					if dfs(neighbor, graph, visited, recr):
						return True
				if recr[neighbor]:
					return True
			recr[node] = False
			return False
		visited = [False for i in range(V)]
		for i in range(V):
			if visited[i] == False:
				if dfs(i, adj, visited, recr):
					return True
		return False


class Solution:

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

		def DFS(node):
			visited[node] = 2
			for adjNode in adj[node]:
				if visited[adjNode] == 0:
					if DFS(adjNode) == 1:
						return 1
				elif visited[adjNode] == 2:
					return 1
			visited[node] = 1
			return 0
		for node in range(V):
			if visited[node] == 0:
				if DFS(node) == 1:
					return 1
		return 0


from collections import deque

class Solution:

	def isCyclic(self, V, adj) -> bool:
		(visited, recSet) = (set(), set())

		def dfs(node) -> bool:
			visited.add(node)
			recSet.add(node)
			for neigh in adj[node]:
				if neigh in recSet:
					return True
				if not neigh in visited:
					if dfs(neigh):
						return True
			recSet.remove(node)
			return False
		for node in range(V):
			if not node in visited:
				recSet.clear()
				if dfs(node):
					return True
		return False


class Solution:

	def isCyclic(self, V, adj):
		colors = [0] * V

		def hasCycle(node: int) -> bool:
			if colors[node] == 1:
				return True
			colors[node] = 1
			for neighbour in adj[node]:
				if colors[neighbour] == 2:
					continue
				if hasCycle(neighbour):
					colors[neighbour] = 0
					return True
			colors[node] = 2
			return False
		for node in range(V):
			if colors[node] == 0:
				if hasCycle(node):
					return True
		return False


from collections import deque

class Solution:

	def isCyclic(self, V, adj):
		indegree = [0] * V
		for neighbours in adj:
			for n in neighbours:
				indegree[n] += 1
		q = deque()
		for (i, v) in enumerate(indegree):
			if v == 0:
				q.append(i)
		count = 0
		while q:
			node = q.popleft()
			count += 1
			for i in adj[node]:
				indegree[i] -= 1
				if indegree[i] == 0:
					q.append(i)
		return True if count != V else False


class Solution:

	def isCyclic(self, V, adj):
		vis = [0] * V
		path = [0] * V
		for i in range(V):
			if vis[i] == 0:
				if self.detect(vis, path, i):
					return True
		return False

	def detect(self, vis, path, ini):
		vis[ini] = 1
		path[ini] = 1
		for x in adj[ini]:
			if vis[x] == 0:
				if self.detect(vis, path, x):
					return True
			elif vis[x] == path[x]:
				return True
		path[ini] = 0
		return False


class Solution:

	def dfs(self, currentNode, visited, pathVisited, adj):
		visited[currentNode] = 1
		pathVisited.append(currentNode)
		for neigh in adj[currentNode]:
			if visited[neigh] == 0:
				answer = self.dfs(neigh, visited, pathVisited, adj)
				if answer:
					return True
			elif visited[neigh] == 1 and neigh in pathVisited:
				return True
		pathVisited.pop()
		return False

	def isCyclic(self, V, adj):
		visited = [0 for j in range(V)]
		pathVisited = []
		for node in range(V):
			if visited[node] == 0:
				answer = self.dfs(node, visited, pathVisited, adj)
				if answer:
					return True
		return False


class Solution:

	def dfs(self, node, adj, V, vis, stk):
		(vis[node], stk[node]) = (True, True)
		for v in adj[node]:
			if stk[v]:
				return True
			if not vis[v] and self.dfs(v, adj, V, vis, stk):
				return True
		stk[node] = False
		return False

	def isCyclic(self, V, adj):
		vis = [False for i in range(V)]
		stk = [False for i in range(V)]
		for i in range(V):
			if vis[i] == False and self.dfs(i, adj, V, vis, stk):
				return True
		return False


from collections import deque

class Solution:

	def isCyclic(self, V, adj):
		indeg = [0 for _ in adj]
		queue = deque()
		for (node, nghs) in enumerate(adj):
			for ngh in nghs:
				indeg[ngh] += 1
		for node in range(len(adj)):
			if indeg[node] == 0:
				queue.append(node)
		processed = 0
		while queue:
			node = queue.popleft()
			processed += 1
			for ngh in adj[node]:
				indeg[ngh] -= 1
				if indeg[ngh] == 0:
					queue.append(ngh)
		return processed != len(adj)


from collections import *

class Solution:

	def isCyclic(self, V, adj):
		indegree = [0] * V
		for node in range(V):
			for adjNode in adj[node]:
				indegree[adjNode] += 1
		q = deque()
		for node in range(V):
			if indegree[node] == 0:
				q.append(node)
		cnt = 0
		while len(q) != 0:
			node = q.popleft()
			cnt += 1
			for adjNode in adj[node]:
				indegree[adjNode] -= 1
				if indegree[adjNode] == 0:
					q.append(adjNode)
		return False if cnt == V else True


from collections import deque

class Solution:

	def isCyclic(self, V, adj):
		indegree = {}
		for src in adj:
			for dest in src:
				indegree[dest] = indegree.get(dest, 0) + 1
		q = deque([])
		for i in range(V):
			if i not in indegree:
				q.append(i)
		cnt = 0
		while q:
			vertex = q.popleft()
			for neighbors in adj[vertex]:
				indegree[neighbors] -= 1
				if indegree[neighbors] == 0:
					q.append(neighbors)
			cnt += 1
		if cnt != V:
			return True
		return False


class Solution:

	def isCyclic(self, V, adj):

		def dfs(v, visited, stack):
			visited[v] = True
			stack[v] = True
			for neighbor in adj[v]:
				if visited[neighbor] == False:
					if dfs(neighbor, visited, stack) == True:
						return True
				elif stack[neighbor] == True:
					return True
			stack[v] = False
			return False
		visited = [False] * V
		stack = [False] * V
		for node in range(V):
			if visited[node] == False:
				if dfs(node, visited, stack) == True:
					return True
		return False


class Solution:

	def dfs(self, node, vis, path, adj):
		vis[node] = 1
		path[node] = 1
		for nei in adj[node]:
			if vis[nei] != 0:
				if path[nei] == 1:
					return True
			elif self.dfs(nei, vis, path, adj):
				return True
		path[node] = 0
		return False

	def isCyclic(self, V, adj):
		vis = [0] * V
		path = [0] * V
		for i in range(V):
			if not vis[i]:
				if self.dfs(i, vis, path, adj):
					return 1
		return 0


class Solution:

	def isCyclic(self, V, adj):
		d = {}
		for i in range(V):
			d[i] = 0
		for i in range(V):
			for j in adj[i]:
				d[j] += 1
		topsort = []
		queue = []
		val = list(d.values())
		for i in range(V):
			if val[i] == 0:
				queue += [i]
		while len(queue) != 0:
			x = queue.pop(0)
			topsort += [x]
			for i in adj[x]:
				d[i] -= 1
				if d[i] == 0:
					queue += [i]
		if len(topsort) == V:
			return False
		return True

		def cyclic(i, recurstack, visited):
			visited[i] = True
			recurstack[i] = True
			for neighbor in adj[i]:
				if visited[neighbor] == False:
					if cyclic(neighbor, recurstack, visited):
						return True
				elif recurstack[neighbor] == True:
					return True
			recurstack[i] = False
			return False
		visited = [False] * (V + 1)
		recurstack = [False] * (V + 1)
		for i in range(len(adj)):
			if visited[i] == False:
				if cyclic(i, recurstack, visited):
					return True
		return False


from collections import deque

class Solution:

	def isCyclic(self, V, adj):
		(topo, indegrees) = ([], [0] * V)
		for adjNodes in adj:
			for adjNode in adjNodes:
				indegrees[adjNode] += 1
		que = deque()
		for node in range(V):
			if indegrees[node] == 0:
				que.append(node)
		while que:
			node = que.popleft()
			topo.append(node)
			for adjNode in adj[node]:
				indegrees[adjNode] -= 1
				if indegrees[adjNode] == 0:
					que.append(adjNode)
		return len(topo) != V


class Solution:

	def dfs(self, node, adj, visited, pathVisited):
		visited[node] = True
		pathVisited[node] = True
		for adjNode in adj[node]:
			if not visited[adjNode]:
				if self.dfs(adjNode, adj, visited, pathVisited):
					return True
			elif pathVisited[adjNode]:
				return True
		pathVisited[node] = False
		return False

	def isCyclic(self, V, adj):
		(visited, pathVisited) = ([False] * V, [False] * V)
		for node in range(V):
			if not visited[node]:
				if self.dfs(node, adj, visited, pathVisited):
					return True
		return False


class Solution:

	def detectCycle(self, node, adj, vis, pathVis):
		vis[node] = 1
		pathVis[node] = 1
		for adjNode in adj[node]:
			if not vis[adjNode]:
				if Solution.detectCycle(self, adjNode, adj, vis, pathVis):
					return True
			elif pathVis[adjNode] == 1:
				return True
		pathVis[node] = 0
		return False

	def isCyclic(self, V, adj):
		vis = [0] * V
		pathVis = [0] * V
		for i in range(V):
			if not vis[i]:
				if Solution.detectCycle(self, i, adj, vis, pathVis):
					return True
		return False


class Solution:

	def dfs(self, vtx, vis, dfsvis, adj):
		vis[vtx] = True
		dfsvis[vtx] = True
		for i in adj[vtx]:
			if vis[i] != True:
				path = self.dfs(i, vis, dfsvis, adj)
				if path:
					return True
			elif dfsvis[i] == True:
				return True
		dfsvis[vtx] = False
		return False

	def isCyclic(self, V, adj):
		vis = [False] * V
		dfsvis = [False] * V
		for i in range(V):
			if vis[i] != True:
				if self.dfs(i, vis, dfsvis, adj):
					return 1
		return 0


from collections import deque

class Solution:

	def isCyclic(self, V, adj):
		inV = [0 for _ in range(V)]
		for i in range(V):
			for v in adj[i]:
				inV[v] += 1
		queue = deque()
		for i in range(V):
			if inV[i] == 0:
				queue.append(i)
		while queue:
			element = queue.popleft()
			for v in adj[element]:
				if inV[v] == 1:
					inV[v] -= 1
					queue.append(v)
				else:
					inV[v] -= 1
		for i in range(V):
			if inV[i] != 0:
				return True
		return False


class Solution:

	def isCyclic(self, V, adj):
		graph = {i: [] for i in range(V)}
		for i in range(V):
			graph[i].extend(adj[i])
		visited = [0] * V
		dfsvisit = [0] * V

		def dfs(node):
			visited[node] = 1
			dfsvisit[node] = 1
			for nei in graph[node]:
				if not visited[nei]:
					if dfs(nei):
						return True
				elif dfsvisit[nei]:
					return True
			dfsvisit[node] = 0
			return False
		for node in range(V):
			if not visited[node]:
				if dfs(node):
					return True
		return False


class Solution:

	def isCyclic(self, V, adj):
		degree = [0] * V
		for i in range(V):
			for j in adj[i]:
				degree[j] += 1
		q = []
		for i in range(V):
			if degree[i] == 0:
				q.append(i)
		c = 0
		while q:
			node = q.pop(0)
			c += 1
			for i in adj[node]:
				degree[i] -= 1
				if degree[i] == 0:
					q.append(i)
		if c == V:
			return False
		else:
			return True


class Solution:

	def DFSUtil(self, adj, v, visited, recStack):
		visited[v] = True
		recStack[v] = True
		for neighbour in adj[v]:
			if visited[neighbour] == False:
				if self.DFSUtil(adj, neighbour, visited, recStack) == True:
					return True
			elif recStack[neighbour] == True:
				return True
		recStack[v] = False
		return False

	def isCyclic(self, V, adj):
		visited = [False] * V
		recStack = [False] * V
		for node in range(V):
			if visited[node] == False:
				if self.DFSUtil(adj, node, visited, recStack) == True:
					return True
		return False


class Solution:

	def check(self, node, V, adj, vis, visdfs):
		vis[node] = 1
		visdfs[node] = 1
		for i in adj[node]:
			if vis[i] != 1:
				k = self.check(i, V, adj, vis, visdfs)
				if k == True:
					return True
			elif visdfs[i] == 1:
				return True
		visdfs[node] = 0
		return False

	def isCyclic(self, V, adj):
		vis = [0] * (V + 1)
		visdfs = [0] * (V + 1)
		for i in range(V):
			if vis[i] != 1:
				k = self.check(i, V, adj, vis, visdfs)
				if k == True:
					return True
		return False


class Solution:

	def isCyclic(self, V, adj):
		isV = [0] * V

		def dete(adj, isV, p, ans):
			isV[p] = 1
			for i in adj[p]:
				if isV[i] == 0:
					dete(adj, isV, i, ans)
				if isV[i] == 1:
					ans[0] = True
					return
			isV[p] = 2
		ans = [False]
		for i in range(V):
			dete(adj, isV, i, ans)
			if ans[0]:
				return True
		return False


class Solution:

	def dfsCheck(self, i, adj, vis, pathvis):
		vis[i] = True
		pathvis[i] = True
		for v in adj[i]:
			if not vis[v]:
				if self.dfsCheck(v, adj, vis, pathvis):
					return True
			if pathvis[v]:
				return True
		pathvis[i] = False
		return False

	def isCyclic(self, V, adj):
		vis = [False for i in range(0, V)]
		pathvis = [False for i in range(0, V)]
		for i in range(0, V):
			if self.dfsCheck(i, adj, vis, pathvis):
				return True


import collections

class Solution:

	def isCyclic(self, V, adj):
		incEdge = [0] * V
		for u in range(V):
			for v in adj[u]:
				incEdge[v] += 1
		q = collections.deque([])
		for (u, inc) in enumerate(incEdge):
			if inc == 0:
				q.append(u)
		ans = []
		while q:
			curr = q.popleft()
			ans.append(curr)
			for v in adj[curr]:
				incEdge[v] -= 1
				if incEdge[v] == 0:
					q.append(v)
		if len(ans) < V:
			return 1
		return 0


class Solution:

	def isCyclic(self, V, adj):
		d = [0] * V
		for i in range(V):
			for j in adj[i]:
				d[j] += 1
		q = []
		for i in range(V):
			if d[i] == 0:
				q.append(i)
		ans = []
		while q:
			a = q.pop(0)
			ans.append(a)
			for i in adj[a]:
				d[i] -= 1
				if d[i] == 0:
					q.append(i)
		if len(ans) == V:
			return False
		return True


from collections import deque, defaultdict

class Solution:

	def dfs(self, node, visited, dfs_call, adj):
		visited[node] = 1
		dfs_call[node] = 1
		for nbr in adj[node]:
			if dfs_call[nbr] == 1:
				return True
			if visited[nbr] == -1:
				ans = self.dfs(nbr, visited, dfs_call, adj)
				if ans:
					return True
		dfs_call[node] = -1
		return False

	def isCyclic1(self, V, adj):
		visited = [-1] * V
		dfs_call = [-1] * V
		for i in range(V):
			if visited[i] == -1:
				ans = self.dfs(i, visited, dfs_call, adj)
				if ans:
					return True
		return False

	def isCyclic(self, V, adj):
		indeg = defaultdict(int)
		for nodes in adj:
			for v in nodes:
				indeg[v] += 1
		visited = [-1] * V
		q = deque()
		for i in range(V):
			if indeg[i] == 0:
				q.append(i)
				visited[i] = 1
		cnt = 0
		while len(q):
			node = q.pop()
			cnt += 1
			for nbr in adj[node]:
				indeg[nbr] -= 1
				if visited[nbr] == -1 and indeg[nbr] == 0:
					q.append(nbr)
					visited[nbr] = 1
		return cnt != V


class Solution:

	def dfs(self, node, visited, dfs_call, adj):
		visited[node] = 1
		dfs_call[node] = 1
		for nbr in adj[node]:
			if dfs_call[nbr] == 1:
				return True
			if visited[nbr] == -1:
				ans = self.dfs(nbr, visited, dfs_call, adj)
				if ans:
					return True
		dfs_call[node] = -1
		return False

	def isCyclic(self, V, adj):
		visited = [-1] * V
		dfs_call = [-1] * V
		for i in range(V):
			if visited[i] == -1:
				ans = self.dfs(i, visited, dfs_call, adj)
				if ans:
					return True
		return False


class Solution:

	def isCyclic(self, V, adj):
		stack = []
		visited = [False] * V
		processed = [[False] * len(adj_vertices) for adj_vertices in adj]
		for vertex in range(V):
			if visited[vertex]:
				continue
			visited[vertex] = True
			stack.append(vertex)
			while len(stack) > 0:
				vertex = stack[-1]
				neighbours = adj[vertex]
				all_visited = True
				for (n_i, neighbour) in enumerate(neighbours):
					if processed[vertex][n_i]:
						continue
					if visited[neighbour]:
						return True
					visited[neighbour] = True
					stack.append(neighbour)
					processed[vertex][n_i] = True
					all_visited = False
					break
				if all_visited:
					visited[vertex] = False
					stack.pop()
		return False


class Solution:

	def isCyclic(self, V, adj):

		def dfs(visit, recs, v, adj):
			visit[v] = True
			recs[v] = True
			for j in adj[v]:
				if not visit[j]:
					if dfs(visit, recs, j, adj):
						return True
				elif recs[j] == True:
					return True
			recs[v] = False
			return False
		visit = [False] * V
		recs = [False] * V
		for i in range(V):
			if not visit[i]:
				if dfs(visit, recs, i, adj):
					return True
		return False


from collections import deque

class Solution:

	def isCyclic(self, V, adj):

		def dfs(adj, visit, path, k):
			path[k] = 1
			visit[k] = 1
			for i in adj[k]:
				if not visit[i]:
					if dfs(adj, visit, path, i) == True:
						return True
				elif path[i] == 1:
					return True
			path[k] = 0
			return False
		visit = [0] * V
		path = [0] * V
		for i in range(V):
			if visit[i] == 0:
				a = dfs(adj, visit, path, i)
				if a == True:
					return True
		return False


class Solution:

	def isCyclic(self, V, adj):
		visited = {}

		def dfs(node):
			if node in visited:
				return visited[node]
			visited[node] = True
			for nei in adj[node]:
				if dfs(nei):
					return True
			visited[node] = False
			return False
		for i in range(V):
			if dfs(i):
				return True
		return False


class Solution:

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

		def dfs(n, visited, dfsvisited):
			for i in adj[n]:
				if dfsvisited[i] == True:
					return True
				elif visited[i] == True:
					continue
				else:
					visited[i] = True
					dfsvisited[i] = True
					if dfs(i, visited, dfsvisited):
						return True
					dfsvisited[i] = False
			return False
		dfsvisited = [False for i in range(V)]
		for i in range(len(adj)):
			if visited[i] == False:
				visited[i] = True
				dfsvisited[i] = True
				if dfs(i, visited, dfsvisited):
					return True
				dfsvisited[i] = False
		return False

		def cyclic(i, recurstack, visited):
			visited[i] = True
			recurstack[i] = True
			for neighbor in adj[i]:
				if visited[neighbor] == False:
					if cyclic(neighbor, recurstack, visited):
						return True
				elif recurstack[neighbor] == True:
					return True
			recurstack[i] = False
			return False
		visited = [False] * (V + 1)
		recurstack = [False] * (V + 1)
		for i in range(len(adj)):
			if visited[i] == False:
				if cyclic(i, recurstack, visited):
					return True
		return False


class Solution:

	def isCyclic(self, V, adj):
		visited = [0] * V
		pathvisited = [0] * V

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


import collections

class Solution:

	def isCyclic(self, V, adj):
		indegree = [0] * V
		count = 0
		que = collections.deque()
		for node in range(V):
			for neighbours in adj[node]:
				indegree[neighbours] += 1
		for (index, value) in enumerate(indegree):
			if value == 0:
				que.append(index)
		while que:
			node = que.popleft()
			count += 1
			for neighbour in adj[node]:
				indegree[neighbour] -= 1
				if indegree[neighbour] == 0:
					que.append(neighbour)
		return not count == V


class Solution:

	def isCyclic(self, V, adj):
		visit = [False] * V
		stack = [False] * V

		def dfs(adj, i, visit, stack):
			visit[i] = True
			stack[i] = True
			for x in adj[i]:
				if stack[x] == True:
					return True
				if visit[x] == False:
					if dfs(adj, x, visit, stack):
						return True
			stack[i] = False
			return False
		for i in range(V):
			if dfs(adj, i, visit, stack):
				return True
		return False


class Solution:

	def isCyclic(self, V, adj):
		visited = [0] * V
		pathvisited = [0] * V

		def dfs(vertex):
			visited[vertex] = 1
			pathvisited[vertex] = 1
			for node in adj[vertex]:
				if visited[node] == 0:
					if dfs(node) == 1:
						return 1
				elif pathvisited[node] == 1:
					return 1
			pathvisited[vertex] = 0
			return 0
		for vertex in range(V):
			if visited[vertex] == 0:
				if dfs(vertex) == 1:
					return 1
		return 0


class Solution:

	def isCyclic(self, V, adj):
		indegree = [0] * V
		for i in adj:
			for j in i:
				indegree[j] += 1
		q = []
		for i in range(V):
			if indegree[i] == 0:
				q.append(i)
		ans = 0
		while q:
			curr = q.pop()
			ans += 1
			for nbr in adj[curr]:
				indegree[nbr] -= 1
				if indegree[nbr] == 0:
					q.append(nbr)
		return not ans == V


class Solution:

	def dfs(self, node, adj, vis, dfsVis):
		vis[node] = True
		dfsVis[node] = True
		for nbr in adj[node]:
			if vis[nbr] == False:
				flag = self.dfs(nbr, adj, vis, dfsVis)
				if flag:
					return True
			elif dfsVis[nbr] == True:
				return True
		dfsVis[node] = False
		return False

	def isCyclic(self, V, adj):
		vis = [False] * V
		dfsVis = [False] * V
		for i in range(V):
			if vis[i] == False:
				flag = self.dfs(i, adj, vis, dfsVis)
				if flag:
					return True
		return False


class Solution:

	def isCyclic(self, V, adj):
		visited = set()
		path = set()

		def dfs(n):
			visited.add(n)
			path.add(n)
			for item in adj[n]:
				if item in path:
					return True
				if item not in visited:
					if dfs(item):
						return True
			path.remove(n)
			return False
		for i in range(V):
			if dfs(i):
				return True
		return False


class Solution:

	def DFS(self, adj, visited, currVisited, node):
		visited.add(node)
		currVisited.add(node)
		for n in adj[node]:
			if n not in visited:
				if self.DFS(adj, visited, currVisited, n):
					return True
			elif n in currVisited:
				return True
		currVisited.remove(node)
		return False

	def isCyclic(self, V, adj):
		visited = set()
		currVisited = set()
		for i in range(V):
			if i not in visited:
				if self.DFS(adj, visited, currVisited, i):
					return True
		return False