Given an undirected graph with V nodes and E edges. The task is to check if there is any cycle in undirected graph.
Note: Solve the problem using disjoint set union(dsu).
 
Example 1:
Input: 
Output: 1
Explanation: There is a cycle between 0->2->4->0
Example 2:
Input: 
Output: 0
Explanation: The graph doesn't contain any cycle
 
Your Task:
You don't need to read or print anyhting. Your task is to complete the function detectCycle() which takes number of vertices in the graph denoting as V and adjacency list denoting as adj and returns 1 if graph contains any cycle otherwise returns 0.
Expected Time Complexity: O(V + E)
Expected Space Complexity: O(V)
 
Constraints:
1 ≤ V, E ≤ 10^{4}

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Spanning trees

Graph algorithms

Data structures

Starter code: class Solution:



    #Function to detect cycle using DSU in an undirected graph.

	def detectCycle(self, V, adj):

		#Code here

Solutions:
class Solution:

	def detectCycle(self, V, adj):
		return find_cycle(adj, V)

def find_parent(x, parent):
	if x == parent[x]:
		return x
	else:
		return find_parent(parent[x], parent)

def compress(x, r, parent):
	if x == parent[x]:
		return x
	else:
		parent[x] = compress(parent[x], r, parent)
		return parent[x]

def is_connected(x, y, parent):
	return find_parent(x, parent) == find_parent(y, parent)

def union(x, y, parent, rank):
	x_par = find_parent(x, parent)
	y_par = find_parent(y, parent)
	if x_par == y_par:
		return 0
	if rank[x_par] >= rank[y_par]:
		parent[y_par] = x_par
		rank[x_par] += 1
	else:
		parent[x_par] = y_par
		rank[y_par] += 1
	return 1

def list_to_edges(G):
	E = []
	for u in range(len(G)):
		for v in G[u]:
			E.append((u, v))
	return E

def find_cycle(G, n):
	if n < 3:
		return 0
	E = list_to_edges(G)
	parent = [i for i in range(n)]
	rank = [0 for i in range(n)]
	for (u, v) in E:
		if is_connected(u, v, parent):
			return 1
		union(u, v, parent, rank)
	return 0


class Solution:

	def detectCycle(self, V, adj):

		def find(node):
			if node == parent[node]:
				return node
			parent[node] = find(parent[node])
			return parent[node]

		def union(u, v):
			pu = find(u)
			pv = find(v)
			if pu == pv:
				return
			if rank[pu] < rank[pv]:
				parent[pu] = pv
			elif rank[pu] > rank[pv]:
				parent[pv] = pu
			else:
				parent[pu] = v
				rank[pv] += 1
		parent = [i for i in range(V)]
		rank = [0] * V
		for u in range(V):
			for v in adj[u]:
				if parent[u] == parent[v] and u < v:
					return 1
				else:
					union(u, v)
		return 0


class Solution:

	def par(self, node, par):
		if node == par[node]:
			return node
		return self.par(par[node], par)

	def union(self, x, y, par, rank):
		u = self.par(x, par)
		v = self.par(y, par)
		if rank[u] < rank[v]:
			par[u] = v
		elif rank[u] > rank[v]:
			par[v] = u
		else:
			par[v] = u
			rank[u] += 1

	def detectCycle(self, V, adj):
		par = [i for i in range(V)]
		rank = [0] * V
		for u in range(V):
			for v in adj[u]:
				if v > u:
					x = self.par(u, par)
					y = self.par(v, par)
					if x == y:
						return 1
					self.union(x, y, par, rank)
		return 0


class Solution:

	def detectCycle(self, V, adj):

		def DFS(adj, u, vis, parent):
			vis[u] = True
			for v in adj[u]:
				if v == parent:
					continue
				if vis[v] == True:
					return True
				if DFS(adj, v, vis, u) == True:
					return True
			return False
		vis = [False] * V
		for i in range(V):
			if not vis[i] and DFS(adj, i, vis, -1) == True:
				return 1
		return 0


from collections import defaultdict

class dsu:

	def __init__(self, size):
		self.parent = [x for x in range(size)]

	def find(self, a):
		if self.parent[a] == a:
			return a
		self.parent[a] = self.find(self.parent[a])
		return self.parent[a]

	def union(self, a, b):
		self.parent[a] = b

class Solution:

	def detectCycle(self, V, adj):
		parent = [x for x in range(V)]

		def union(a, b):
			parent[a] = b

		def Find(a):
			if parent[a] == a:
				return a
			return Find(parent[a])
		for x in range(V):
			for y in adj[x]:
				if y >= x:
					a = Find(x)
					b = Find(y)
					if a == b:
						return 1
					union(a, b)
		return 0


from collections import defaultdict

class Solution:

	def get_all_edges(self, adj):
		_all_edges = set()
		for (u, v_list) in enumerate(adj):
			for v in v_list:
				if u < v:
					_all_edges.add((u, v))
				else:
					_all_edges.add((v, u))
		return _all_edges

	def get_key(self, u):
		for key in self.disjoint_set:
			if u in self.disjoint_set[key]:
				return key
		return None

	def key_if_None(self, key, v):
		if not key:
			self.key_counter += 1
			key = self.key_counter
		self.disjoint_set[key].add(v)
		return key

	def merge(self, u_key, v_key):
		s1 = self.disjoint_set[u_key]
		s2 = self.disjoint_set[v_key]
		s = s1.union(s2)
		self.disjoint_set[u_key] = s
		del self.disjoint_set[v_key]

	def detectCycle(self, V, adj):
		all_edges = self.get_all_edges(adj)
		self.disjoint_set = defaultdict(set)
		self.key_counter = 0
		for e in all_edges:
			(u, v) = e
			(u_key, v_key) = (self.get_key(u), self.get_key(v))
			if u_key and v_key and (u_key == v_key):
				return 1
			u_key = self.key_if_None(u_key, u)
			v_key = self.key_if_None(v_key, v)
			self.merge(u_key, v_key)
		return 0


class Solution:

	def __init__(self):
		self.parent = []
		self.rank = []

	def initialize(self, V):
		for i in range(V):
			self.parent.append(i)
			self.rank.append(0)

	def findParent(self, node):
		if self.parent[node] == node:
			return node
		self.parent[node] = self.findParent(self.parent[node])
		return self.parent[node]

	def union(self, u, v):
		u = self.findParent(u)
		v = self.findParent(v)
		if self.rank[u] > self.rank[v]:
			self.parent[v] = u
		elif self.rank[v] > self.rank[u]:
			self.parent[u] = v
		else:
			self.parent[v] = u
			self.rank[u] = self.rank[u] + 1

	def detectCycle(self, V, adj):
		self.initialize(V)
		if V < 3:
			return 0
		for u in range(V):
			for v in adj[u]:
				parent_u = self.findParent(u)
				parent_v = self.findParent(v)
				if parent_u == parent_v:
					return 1
				else:
					self.union(u, v)
		return 0


class Solution:

	def detectCycle(self, V, adj):
		par = [i for i in range(V)]

		def find(u):
			while par[u] != u:
				u = par[u]
			return u

		def union(x, y):
			par[x] = y
		edges = set()
		for u in range(V):
			for v in adj[u]:
				edges.add((min(u, v), max(u, v)))
		for e in edges:
			u = find(e[0])
			v = find(e[1])
			if u == v:
				return 1
			union(u, v)
		return 0


class Solution:

	def detectCycle(self, V, adj):

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


class Solution:

	def detectCycle(self, V, adj):
		parent = [i for i in range(V)]
		rank = [1] * V

		def find(x):
			if parent[x] != x:
				parent[x] = find(parent[x])
			return parent[x]

		def union(x, y):
			a = find(x)
			b = find(y)
			if a == b:
				return 1
			if rank[a] < rank[b]:
				parent[a] = b
				rank[b] += rank[a]
			else:
				parent[b] = a
				rank[a] += rank[b]
			return 0
		for (u, v) in adj:
			if union(u, v):
				return 1
		return 0


class Solution:

	def find(self, parent, val):
		while parent[val] != val:
			val = parent[val - 1]
		return val

	def union(self, parent, val1, val2):
		x = self.find(parent, val1)
		y = self.find(parent, val2)
		if x == y:
			return True
		parent[x - 1] = y
		return False

	def detectCycle(self, V, adj):
		parent = [*range(V)]
		for i in range(V):
			for j in adj[i]:
				if self.union(parent, j, i):
					return 1
		return 0


class Solution:

	def find(self, parent, val):
		while parent[val] != val:
			val = parent[val - 1]
		return val

	def union(self, parent, val1, val2):
		x = self.find(parent, val1)
		y = self.find(parent, val2)
		if x == y:
			return True
		parent[x - 1] = y
		return False

	def detectCycle(self, V, adj):
		parent = [*range(V)]
		vis = [0] * (V + 1)
		for i in range(V):
			if vis[i] == 0:
				q = [i]
				fl = None
				while len(q):
					root = q.pop(0)
					vis[root] = 1
					for child in adj[root]:
						if vis[child] == 0:
							fl = self.union(parent, child, root)
							if fl:
								return 1
							q.append(child)
		return 0


class Solution:

	def detectCycle(self, V, adj):
		visited = [False] * V
		for nodes in adj:
			if all([visited[n] for n in nodes]):
				return 1
			for n in nodes:
				visited[n] = True
		return 0


class Solution:

	def detectCycle(self, V, adj):
		p = [i for i in range(V)]

		def par(v):
			if v == p[v]:
				return v
			if v == p[v]:
				return par(p[v])

		def union(x, y):
			p[x] = y
		for i in range(len(adj)):
			for j in adj[i]:
				if par(i) == par(j):
					return 1
				union(i, j)
		return 0


class Solution:

	def find_parent(self, parent, node):
		if node == parent[node]:
			return node
		return self.find_parent(parent, parent[node])

	def detectCycle(self, V, adj):
		edge_list = set()
		for i in range(len(adj)):
			for neighbour in adj[i]:
				if neighbour < i:
					edge_list.add((neighbour, i))
				else:
					edge_list.add((i, neighbour))
		parents = [-1] * V
		for i in range(V):
			parents[i] = i
		for edge in edge_list:
			x = self.find_parent(parents, edge[0])
			y = self.find_parent(parents, edge[1])
			if x == y:
				return 1
			parents[x] = y
		return 0


class Solution:

	def Find(self, u, parent):
		if parent[u] == u:
			return u
		parent[u] = self.Find(parent[u], parent)
		return parent[u]

	def Union(self, a, b, parent, rank):
		if rank[a] > rank[b]:
			parent[b] = a
		elif rank[a] < rank[b]:
			parent[a] = b
		else:
			rank[a] += 1
			parent[b] = a

	def detectCycle(self, V, adj):
		parent = [int(i) for i in range(V)]
		rank = [0] * V
		for i in range(V):
			for j in range(len(adj[i])):
				if i < adj[i][j]:
					p1 = self.Find(i, parent)
					p2 = self.Find(adj[i][j], parent)
					if p1 == p2:
						return 1
					else:
						self.Union(p1, p2, parent, rank)
		return 0


class Solution:

	def detectCycle(self, V, adj):
		par = [i for i in range(V)]
		rank = [1 for i in range(V)]
		for u in range(V):
			for v in adj[u]:
				if u < v and self.union(u, v, par, rank):
					return 1
		return 0

	def union(self, a, b, par, rank):
		repa = self.find(a, par)
		repb = self.find(b, par)
		if repa == repb:
			return True
		if rank[repa] == rank[repb]:
			par[repb] = repa
			rank[repa] += 1
		elif rank[repa] < rank[repb]:
			par[repa] = repb
		else:
			par[repb] = repa
		return False

	def find(self, a, par):
		while a != par[a]:
			a = par[a]
		return par[a]


class Solution:

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

		def dfs(node, parent):
			visited[node] = 1
			for i in adj[node]:
				if visited[i] == 1 and i != parent:
					return 1
				if visited[i] == 0 and dfs(i, node) == 1:
					return 1
			return 0
		ans = 0
		for i in range(V):
			if visited[i] == 0:
				ans += dfs(i, -1)
		return 1 if ans > 0 else 0


class Solution:

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

	def union(self, parent, rank, u, v):
		if rank[u] > rank[v]:
			parent[v] = u
		elif rank[u] < rank[v]:
			parent[u] = v
		else:
			parent[u] = v
			rank[v] += 1

	def detectCycle(self, V, adj):
		parent = list(range(V))
		rank = [0] * V
		edge = set()
		for u in range(V):
			for v in adj[u]:
				if (u, v) in edge or (v, u) in edge:
					continue
				edge.add((u, v))
				edge.add((v, u))
				u_parent = self.find(parent, u)
				v_parent = self.find(parent, v)
				if u_parent == v_parent:
					return 1
				self.union(parent, rank, u_parent, v_parent)
		return 0


class Solution:

	def find_set(self, v, parent):
		if v != parent[v]:
			v = self.find_set(parent[v], parent)
		return v

	def unionn(self, x, y, parent, rank):
		x = self.find_set(x, parent)
		y = self.find_set(y, parent)
		if rank[x] < rank[y]:
			[x, y] = [y, x]
		parent[y] = x
		rank[x] = rank[x] + rank[y]

	def detectCycle(self, V, adj):
		parent = [i for i in range(V)]
		rank = [1 for i in range(V)]
		s = set(tuple([-1, -1]))
		for u in range(V):
			for v in adj[u]:
				if tuple([u, v]) in s or tuple([v, u]) in s:
					continue
				s.add(tuple([u, v]))
				u1 = u
				v1 = v
				x = self.find_set(u1, parent)
				y = self.find_set(v1, parent)
				if x == y:
					return 1
				self.unionn(x, y, parent, rank)
		return 0


class Solution:

	def Find(self, x, parent):
		if parent[x] != x:
			parent[x] = self.Find(parent[x], parent)
		return parent[x]

	def Union(self, x, y, rank, parent):
		parentx = self.Find(x, parent)
		parenty = self.Find(y, parent)
		if parentx == parenty:
			return 1
		if rank[parentx] > rank[parenty]:
			parent[y] = parentx
		elif rank[parenty] > rank[parentx]:
			parent[x] = parenty
		else:
			parent[y] = parentx
			rank[parentx] += 1
		return 0

	def makeEdge(self, V, adj):
		edge = []
		visited = [-1 for i in range(V)]
		for parent in range(V):
			visited[parent] = 1
			for child in adj[parent]:
				if visited[child] == -1:
					edge.append([parent, child])
		return edge

	def isCycle(self, V, adj):
		parent = [i for i in range(V)]
		rank = [0 for i in range(V)]
		edge = self.makeEdge(V, adj)
		for ed in edge:
			x = ed[0]
			y = ed[1]
			ans = self.Union(x, y, rank, parent)
			if ans:
				return 1
		return 0

	def detectCycle(self, V, adj):
		return self.isCycle(V, adj)


class Solution:

	def __init__(self):
		self.parent = []
		self.rank = []

	def find(self, x):
		if self.parent[x] == x:
			return x
		self.parent[x] = self.find(self.parent[x])
		return self.parent[x]

	def union(self, x, y):
		x_parent = self.find(x)
		y_parent = self.find(y)
		if self.rank[x_parent] > self.rank[y_parent]:
			self.parent[y_parent] = x_parent
		elif self.rank[x_parent] < self.rank[y_parent]:
			self.parent[x_parent] = y_parent
		else:
			self.parent[x_parent] = y_parent
			self.rank[y_parent] += 1

	def detectCycle(self, V, adj):
		self.parent = [i for i in range(V)]
		self.rank = [0] * V
		for u in range(V):
			for v in adj[u]:
				if u < v:
					if self.find(u) == self.find(v):
						return 1
					else:
						self.union(u, v)
		return 0


class Solution:

	def detectCycle(self, V, adj):
		visit = set()
		self.ans = False

		def dfs(n, par):
			visit.add(n)
			for i in adj[n]:
				if i not in visit:
					dfs(i, n)
					return
				elif par != i:
					self.ans = 1
					return
		for i in range(V):
			if i not in visit:
				dfs(i, -1)
				if self.ans:
					return 1
		return 0


class Solution:

	def detectCycle(self, V, adj):
		parent = [i for i in range(V)]
		rank = [0 for i in range(V)]
		vis = set()
		for i in range(V):
			for y in adj[i]:
				if (y, i) in vis:
					continue
				vis.add((i, y))
				i_r = self.find(parent, i)
				y_r = self.find(parent, y)
				if i_r == y_r:
					return 1
				self.union(parent, rank, i_r, y_r)
		return 0

	def find(self, parent, x):
		if parent[x] == x:
			return x
		parent[x] = self.find(parent, parent[x])
		return parent[x]

	def union(self, parent, rank, a, b):
		a_r = self.find(parent, a)
		b_r = self.find(parent, b)
		if a_r != b_r:
			if rank[a_r] < rank[b_r]:
				parent[a_r] = b_r
			elif rank[b_r] < rank[a_r]:
				parent[b_r] = a_r
			else:
				parent[a_r] = b_r
				rank[b_r] += 1


class Solution:

	def detectCycle(self, V, adj):
		s = set()
		for i in adj:
			l1 = len(s)
			l2 = len(i)
			s = s.union(i)
			if len(s) != l1 + l2:
				return 1
		return 0


class Solution:

	def find_parent(self, v, parent):
		if v != parent[v]:
			return self.find_parent(parent[v], parent)
		return parent[v]

	def union(self, v1, v2, parent, rank):
		v1par = self.find_parent(v1, parent)
		v2par = self.find_parent(v2, parent)
		if rank[v1par] > rank[v2par]:
			parent[v2par] = v1par
		elif rank[v2par] > rank[v1par]:
			parent[v1par] = v2par
		else:
			parent[v2par] = v1par
			rank[v1par] += 1

	def detectCycle(self, V, adj):
		parent = [v for v in range(V)]
		rank = [1 for _ in range(V)]
		for v in range(V):
			for nbrv in adj[v]:
				par_v = self.find_parent(v, parent)
				par_nbrv = self.find_parent(nbrv, parent)
				if par_v == par_nbrv and v < nbrv:
					return 1
				else:
					self.union(v, nbrv, parent, rank)
		return 0


class Solution:

	def detectCycle(self, V, adj):
		s = [0] * V
		for n in range(V):
			if s[n] == 0 and dfs(n, adj, None, s):
				return 1
		return 0

def dfs(n, adj, p, s):
	if s[n] == 2:
		return False
	if s[n] == 1:
		return True
	s[n] = 1
	for nei in adj[n]:
		if nei != p and dfs(nei, adj, n, s):
			return True
	s[n] = 2
	return False


class Solution:

	def detectCycle(self, V, adj):

		def findPar(x, par):
			if x != par[x]:
				par[x] = findPar(par[x], par)
			return par[x]

		def union(a, b, par, rank):
			ap = findPar(a, par)
			bp = findPar(b, par)
			if ap == bp:
				return
			if rank[ap] > rank[bp]:
				par[bp] = par[ap]
			elif rank[bp] > rank[ap]:
				par[ap] = par[bp]
			else:
				par[ap] = par[bp]
				rank[bp] += 1
		visited = [-1 for i in range(V)]
		par = [i for i in range(V)]
		rank = [1 for i in range(V)]
		for a in range(V):
			ap = findPar(a, par)
			visited[a] = 1
			for b in adj[a]:
				if visited[b] == -1:
					bp = findPar(b, par)
					if ap == bp:
						return 1
					union(ap, bp, par, rank)
		return 0


class Solution:

	def detectCycle(self, V, adj):
		par = [i for i in range(V)]
		size = [1 for i in range(V)]
		visited = set()
		for i in range(V):
			parent2 = self.findParent(i, par)
			for node in adj[i]:
				if str(node) + ' ' + str(i) in visited:
					continue
				parent1 = self.findParent(node, par)
				if parent1 == parent2:
					return 1
				if size[parent2] < size[parent1]:
					par[parent2] = parent1
					size[parent1] += size[parent2]
				else:
					par[parent1] = parent2
					size[parent2] += size[parent1]
				visited.add(str(i) + ' ' + str(node))
		return 0

	def findParent(self, node, par):
		if par[node] == node:
			return node
		return self.findParent(par[node], par)


class Solution:

	def detectCycle(self, V, adj):

		def find_set(x, par):
			if par[x] == x:
				return x
			return find_set(par[x], par)

		def union(x, y, par, rank):
			x = find_set(x, par)
			y = find_set(y, par)
			if x == y:
				return True
			rank[x] += rank[y]
			par[y] = x
			return False
		par = [i for i in range(V)]
		rank = [1 for _ in range(V)]
		for node in range(V):
			for neighb in adj[node]:
				if neighb <= node:
					continue
				if union(node, neighb, par, rank):
					return 1
		return 0


class Solution:

	def findSet(self, i, par):
		if i == par[i]:
			return i
		ans = self.findSet(par[i], par)
		par[i] = ans
		return ans

	def union_(self, a, b, par, rank1):
		a = self.findSet(a, par)
		b = self.findSet(b, par)
		if a != b:
			if rank1[a] < rank1[b]:
				(a, b) = (b, a)
			rank1[a] += rank1[b]
			par[b] = a

	def detectCycle(self, V, adj):
		parent = [i for i in range(V)]
		rank = [0] * V
		for i in range(V):
			for j in adj[i]:
				if self.findSet(i, parent) == self.findSet(j, parent) and i < j:
					return 1
				else:
					self.union_(i, j, parent, rank)
		return 0


class Solution:

	def detectCycle(self, V, adj):
		parent = [i for i in range(V)]
		immediate_parent = [-1 for i in range(V)]
		stack = []
		visited = []
		for node in range(V):
			if node not in visited:
				stack.append(node)
				if self.detectCycleRec(V, adj, parent, immediate_parent, stack, visited) == 1:
					return 1
		return 0

	def detectCycleRec(self, V, adj, parent, immediate_parent, stack, visited):
		node = stack.pop()
		visited.append(node)
		for next_node in adj[node]:
			x = self.find(node, parent)
			y = self.find(next_node, parent)
			if x == y and immediate_parent[node] != next_node:
				return 1
			elif immediate_parent[node] != next_node:
				self.union(x, y, parent)
				immediate_parent[next_node] = node
				stack.append(next_node)
				if self.detectCycleRec(V, adj, parent, immediate_parent, stack, visited) == 1:
					return 1
		return 0

	def union(self, x, y, parent):
		parent[y] = x

	def find(self, x, parent):
		if parent[x] == x:
			return x
		else:
			return self.find(parent[x], parent)


class Solution:

	def find_parent(self, parent, u):
		if u != parent[u]:
			parent[u] = self.find_parent(parent, parent[u])
		return parent[u]

	def union(self, u, v, parent, rank):
		u = self.find_parent(parent, u)
		v = self.find_parent(parent, v)
		if u == v:
			return
		if rank[u] < rank[v]:
			parent[u] = v
		elif rank[v] < rank[u]:
			parent[v] = u
		else:
			parent[u] = v
			rank[v] += 1

	def detectCycle(self, V, adj):
		parent = [i for i in range(V)]
		rank = [0 for i in range(V)]
		for i in range(V):
			for j in adj[i]:
				x = self.find_parent(parent, i)
				y = self.find_parent(parent, j)
				if x == y and i < j:
					return 1
				self.union(x, y, parent, rank)
		return 0


class Solution:

	def detectCycle(self, V, adj):
		par = [i for i in range(V)]
		rank = [1 for i in range(V)]
		for a in range(V):
			for b in adj[a]:
				if a <= b and self.iscon(a, b, par):
					return 1
				self.union(a, b, par, rank)
		return 0

	def union(self, a, b, par, rank):
		a = self.ancestor(a, par)
		b = self.ancestor(b, par)
		if rank[a] > rank[b]:
			par[b] = a
			rank[a] += rank[b]
		else:
			par[a] = b
			rank[b] += rank[a]

	def ancestor(self, node, par):
		if par[node] == node:
			return node
		par[node] = self.ancestor(par[node], par)
		return par[node]

	def iscon(self, a, b, par):
		return self.ancestor(a, par) == self.ancestor(b, par)


from collections import defaultdict

class Solution:

	def detectCycle(self, V, adj):
		self.dictParent = defaultdict(int)
		self.rank = defaultdict(int)
		self.count = 0
		edges = set()
		for a in range(V):
			for b in adj[a]:
				if (a, b) not in edges and (b, a) not in edges:
					edges.add((a, b))
		for (a, b) in edges:
			if self.connect(a, b):
				return 1
		return 0

	def insert(self, a):
		if a not in self.dictParent:
			self.dictParent[a] = a
			self.rank[a] = self.count
			self.count += 1

	def getParent(self, a):
		if a in self.dictParent:
			if self.dictParent[a] != a:
				self.dictParent[a] = self.getParent(self.dictParent[a])
		else:
			self.insert(a)
		return self.dictParent[a]

	def connect(self, a, b):
		pa = self.getParent(a)
		pb = self.getParent(b)
		if pa == pb:
			res = True
		else:
			res = False
			if self.rank[pb] < self.rank[pa]:
				self.dictParent[pa] = pb
			elif self.rank[pb] > self.rank[pa]:
				self.dictParent[pb] = pa
			else:
				self.dictParent[pa] = pb
				self.rank[pa] += 1
		return res


class Solution:

	def find(self, i, parent):
		if parent[i] == i:
			return i
		return self.find(parent[i], parent)

	def Union(self, x, y, parent):
		xset = self.find(x, parent)
		yset = self.find(y, parent)
		parent[xset] = yset

	def approach1(self, V, adj):
		parent = [-1] * V
		for i in range(V):
			parent[i] = i
		for u in range(V):
			for v in adj[u]:
				if u < v:
					parent_i = self.find(u, parent)
					parent_neg = self.find(v, parent)
					if parent_i == parent_neg:
						return 1
					else:
						self.Union(parent_i, parent_neg, parent)
		return 0

	def detectCycle(self, V, adj):
		return self.approach1(V, adj)


class Solution:

	def find_root(self, node, par):
		if node != par[node]:
			par[node] = self.find_root(par[node], par)
		return par[node]

	def is_connected(self, node1, node2, par):
		return self.find_root(node1, par) == self.find_root(node2, par)

	def connect(self, node1, node2, par, rank):
		node1 = self.find_root(node1, par)
		node2 = self.find_root(node2, par)
		if rank[node1] > rank[node2]:
			par[node2] = node1
			rank[node1] += rank[node2]
		else:
			par[node1] = node2
			rank[node2] += rank[node1]

	def detectCycle(self, V, adj):
		rank = [1 for i in range(V)]
		par = [i for i in range(V)]
		for i in range(V):
			for j in adj[i]:
				if j >= i and self.is_connected(i, j, par):
					return 1
				self.connect(i, j, par, rank)
		return 0


class Solution:

	def detectCycle(self, V, adj):

		def set_parent(x):
			if x != parent[x]:
				parent[x] = set_parent(parent[x])
			return parent[x]

		def unionn(x, y):
			(x, y) = (set_parent(x), set_parent(y))
			if rank[x] < rank[y]:
				(x, y) = (y, x)
			parent[y] = x
			rank[x] += rank[y]
		parent = [i for i in range(V)]
		rank = [1 for _ in range(V)]
		visited = set((-1, -1))
		for node in range(V):
			for neighbor in adj[node]:
				if (node, neighbor) not in visited and (neighbor, node) not in visited:
					visited.add((node, neighbor))
					(x, y) = (set_parent(node), set_parent(neighbor))
					if x == y:
						return 1
					unionn(x, y)
		return 0


class Solution:

	def detectCycle(self, V, adj):

		def set_parent(v):
			if v != parent[v]:
				v = set_parent(parent[v])
			return v

		def unionn(x, y):
			x = set_parent(x)
			y = set_parent(y)
			if rank[x] < rank[y]:
				(x, y) = (y, x)
			parent[y] = x
			rank[x] += rank[y]
		parent = [i for i in range(V)]
		rank = [1 for _ in range(V)]
		visited = set((-1, -1))
		for node in range(V):
			for neighbor in adj[node]:
				if not ((node, neighbor) in visited or (neighbor, node) in visited):
					visited.add((node, neighbor))
					(node1, neighbor1) = (node, neighbor)
					x = set_parent(node1)
					y = set_parent(neighbor1)
					if x == y:
						return 1
					unionn(x, y)
		return 0


class Solution:

	def detectCycle(self, V, adj):

		def find_set(v):
			if v != parent[v]:
				v = find_set(parent[v])
			return v

		def unionn(x, y):
			x = find_set(x)
			y = find_set(y)
			if rank[x] < rank[y]:
				(x, y) = (y, x)
			parent[y] = x
			rank[x] += rank[y]
		parent = [i for i in range(V)]
		rank = [1 for _ in range(V)]
		s = set((-1, -1))
		for node in range(V):
			for neighbor in adj[node]:
				if (node, neighbor) in s or (neighbor, node) in s:
					continue
				s.add((node, neighbor))
				(node1, neighbor1) = (node, neighbor)
				x = find_set(node1)
				y = find_set(neighbor1)
				if x == y:
					return 1
				unionn(x, y)
		return 0


class DSU:

	def __init__(self, n):
		self.parent = [i for i in range(n + 1)]
		self.rank = [0 for i in range(n + 1)]
		self.cnt = n
		self.size = [1 for i in range(n + 1)]
		self.curMax = 1
		self.curMin = 1

	def find(self, x):
		if self.parent[x] == x:
			return x
		self.parent[x] = self.find(self.parent[x])
		return self.parent[x]

	def union(self, u, v):
		x_rep = self.find(u)
		y_rep = self.find(v)
		if x_rep == y_rep:
			return
		self.cnt -= 1
		if self.rank[x_rep] > self.rank[y_rep]:
			self.parent[y_rep] = x_rep
			self.size[x_rep] += self.size[y_rep]
			self.size[y_rep] = 0
		elif self.rank[x_rep] < self.rank[y_rep]:
			self.parent[x_rep] = y_rep
			self.size[y_rep] += self.size[x_rep]
			self.size[x_rep] = 0
		else:
			self.parent[y_rep] = x_rep
			self.rank[x_rep] += 1
			self.size[x_rep] += self.size[y_rep]
			self.size[y_rep] = 0
		self.curMin = min(self.curMin, self.size[x_rep], self.size[y_rep])
		self.curMax = max(self.curMax, self.size[x_rep], self.size[y_rep])

	def maxSize(self):
		return self.curMax

	def minSize(self):
		return self.curMin

	def countSets(self):
		return self.cnt

class Solution:

	def detectCycle(self, V, adj):
		if V == 1:
			return 0
		indegree = 0
		for i in range(V):
			indegree += len(adj[i])
		if indegree == 2 * (V - 2) + 2:
			return 0
		return 1


class Solution:

	def detectCycle(self, V, adj):
		if V <= 2:
			return 0

		def findparent(parent, node):
			if parent[node] == node:
				return node
			return findparent(parent, parent[node])

		def union(parent, a, b):
			parent[b] = a
		parent = [node for node in range(V)]
		for i in range(V):
			x = findparent(parent, i)
			for j in adj[i]:
				y = findparent(parent, j)
				if x == y:
					return 1
				union(parent, i, j)
		return 0


class Solution:

	def detectCycle(self, V, adj):
		visited = set()

		def helper(cur, par):
			visited.add(cur)
			for nei in adj[cur]:
				if nei not in visited:
					if helper(nei, cur):
						return True
				elif par != nei:
					return True
			return False
		for i in range(V):
			if i not in visited:
				if helper(i, -1):
					return 1
		return 0


class Solution:

	def find(self, x, parent):
		if parent[x] == x:
			return x
		else:
			return self.find(parent[x], parent)

	def union(self, x, y, parent):
		par_x = self.find(x, parent)
		par_y = self.find(y, parent)
		if par_x == par_y:
			return True
		else:
			parent[par_x] = par_y
			return False

	def detectCycle(self, v, adj):
		parent = [x for x in range(v)]
		edge_set = set()
		for (i, nodes) in enumerate(adj):
			for x in nodes:
				if (i, x) not in edge_set and (x, i) not in edge_set:
					edge_set.add((i, x))
					flag = self.union(i, x, parent)
					if flag == True:
						return 1
		return 0


class Solution:

	def detectCycle(self, V, adj):

		def findParent(x, par):
			if par[x] != x:
				par[x] = findParent(par[x], par)
			return par[x]

		def union(x, y, par, rank):
			px = findParent(x, par)
			py = findParent(y, par)
			if px == py:
				return
			if rank[px] > rank[py]:
				par[py] = px
			elif rank[py] > rank[px]:
				par[px] = py
			else:
				par[px] = py
				rank[py] += 1
		par = [i for i in range(V)]
		rank = [0 for i in range(V)]
		visited = [-1 for i in range(V)]
		for a in range(V):
			ap = findParent(a, par)
			visited[a] = 1
			for b in adj[a]:
				if visited[b] == -1:
					bp = findParent(b, par)
					if ap == bp:
						return 1
					union(ap, bp, par, rank)
		return 0


class Solution:

	def detectCycle(self, V, adj):

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


class Solution:

	def detectCycle(self, V, adj):
		par = [i for i in range(V)]
		real_parent = [i for i in range(V)]
		for i in range(V):
			for j in adj[i]:
				par_i = i
				par_j = j
				real_parent[j] = i
				while par[par_i] != par_i:
					par_i = par[par_i]
				while par[par_j] != par_j:
					par_j = par[par_j]
				if par_i == par_j and real_parent[i] != j:
					return 1
				else:
					par[par_i] = par_j
		return 0


class Solution:

	def union(self, parent, x, y):
		parent[x] = y

	def find_parent(self, parent, node):
		if parent[node] == node:
			return node
		return self.find_parent(parent, parent[node])

	def detectCycle(self, V, adj):
		parent = [i for i in range(V)]
		for i in range(V):
			for j in adj[i]:
				x = self.find_parent(parent, i)
				y = self.find_parent(parent, j)
				if x == y and i < j:
					return 1
				self.union(parent, x, y)
		return 0


class Solution:

	def union(self, x, y, parent):
		parent_x = self.find(x, parent)
		parent_y = self.find(y, parent)
		parent[parent_x] = parent_y

	def find(self, x, parent):
		if parent[x] == x:
			return x
		else:
			return self.find(parent[x], parent)

	def detectCycle(self, v, adj):
		edges = set()
		parent = [i for i in range(v)]
		for i in range(v):
			for j in adj[i]:
				if (i, j) not in edges and (j, i) not in edges:
					edges.add((i, j))
					x = self.find(i, parent)
					y = self.find(j, parent)
					if x == y:
						return 1
					self.union(i, j, parent)
		return 0


class Solution:

	def detectCycle(self, v, adj):
		par = {i: i for i in range(v)}
		rank = {i: 1 for i in range(v)}

		def find(n1):
			while n1 != par[n1]:
				par[n1] = par[par[n1]]
				n1 = par[n1]
			return n1

		def union(n1, n2):
			(p1, p2) = (find(n1), find(n2))
			if p1 == p2:
				return 0
			if rank[p1] < rank[p2]:
				(p1, p2) = (p2, p1)
			par[p2] = p1
			rank[p1] += rank[p2]
			return 1
		for (idx, vals) in enumerate(adj):
			for i in vals:
				if not union(idx, i) and idx < i:
					return 1
		return 0


class Solution:

	def detectCycle(self, V, adj):
		visited = [0] * V
		for i in range(0, V):
			if not visited[i]:
				if find(i, visited, -1, adj) == 1:
					return 1
		return 0

def find(node, visited, parent, adj):
	visited[node] = 1
	for i in adj[node]:
		if not visited[i]:
			if find(i, visited, node, adj):
				return 1
		elif i != parent:
			return 1
	return 0


def find_parent(i, parent):
	if parent[i] == -1:
		return i
	return find_parent(parent[i], parent)

def union(s1, s2, parent):
	parent[s2] = s1

class Solution:

	def detectCycle(self, n, adj):
		edges = set()
		for i in range(n):
			for node in adj[i]:
				if node < i:
					edges.add((node, i))
				else:
					edges.add((i, node))
		parent = [-1 for i in range(n)]
		flag = 0
		for e in edges:
			s1 = find_parent(e[0], parent)
			s2 = find_parent(e[1], parent)
			if s1 != s2:
				union(s1, s2, parent)
			else:
				flag = 1
				break
		return flag


class Solution:

	def detectCycle(self, V, adj):
		parent = dict()
		for i in range(V):
			parent[i] = i
		visited = dict()
		for i in range(V):
			for j in adj[i]:
				if (i, j) in visited or (j, i) in visited:
					continue
				visited[i, j] = True
				x = self.findParent(i, parent)
				y = self.findParent(j, parent)
				if x == y:
					return 1
				parent[x] = y
		return 0

	def findParent(self, i, parent):
		if i == parent[i]:
			return i
		parent[i] = self.findParent(parent[i], parent)
		return parent[i]


class Solution:

	def detectCycle(self, V, adj):
		par = [i for i in range(V)]
		rank = [i for i in range(V)]
		visited = [-1 for i in range(V)]

		def findParent(x, par):
			if par[x] != x:
				par[x] = findParent(par[x], par)
			return par[x]

		def union(a, b, par, rank):
			pa = findParent(a, par)
			pb = findParent(b, par)
			if pa == pb:
				return
			if rank[pa] > rank[pb]:
				par[pb] = par[pa]
			elif rank[pb] > rank[pa]:
				par[pa] = par[pb]
			else:
				par[pa] = par[pb]
				rank[pb] += 1
		for a in range(V):
			pa = findParent(a, par)
			visited[a] = 1
			for b in adj[a]:
				if visited[b] == -1:
					pb = findParent(b, par)
					if pa == pb:
						return 1
					else:
						union(pa, pb, par, rank)
		return 0


class Solution:

	def initialization(self, V):
		self.parent = [i for i in range(V)]
		self.rank = [1] * V

	def find_(self, a):
		if a == self.parent[a]:
			return a
		self.parent[a] = self.find_(self.parent[a])
		return self.parent[a]

	def union_(self, a, b, a_rep, b_rep):
		if self.rank[a_rep] > self.rank[b_rep]:
			self.parent[b] = a
		elif self.rank[a_rep] < self.rank[b_rep]:
			self.parent[a] = b
		else:
			self.parent[a] = b
			self.rank[b_rep] += 1

	def detectCycle(self, V, adj):
		self.initialization(V)
		for i in range(V):
			for j in adj[i]:
				(x_rep, y_rep) = (self.find_(i), self.find_(j))
				if x_rep == y_rep:
					if i < j:
						return 1
				else:
					self.union_(i, j, x_rep, y_rep)
		return 0


class Solution:

	def get_leader(self, leader, i):
		if leader[i] != i:
			leader[i] = self.get_leader(leader, leader[i])
		return leader[i]

	def union(self, leader, rank, u, v):
		if rank[u] > rank[v]:
			leader[v] = u
		elif rank[v] > rank[u]:
			leader[u] = v
		else:
			leader[v] = u
			rank[u] += 1

	def detectCycle(self, V, adj):
		edges = []
		hash_map = {}
		for i in range(len(adj)):
			for j in adj[i]:
				if (i, j) not in hash_map and (j, i) not in hash_map:
					edges.append([i, j])
					hash_map[i, j] = 1
					hash_map[j, i] = 1
		rank = [0] * V
		leader = [0] * V
		for i in range(V):
			leader[i] = i
		for i in range(len(edges)):
			(u, v) = (edges[i][0], edges[i][1])
			(x, y) = (self.get_leader(leader, u), self.get_leader(leader, v))
			if x != y:
				self.union(leader, rank, x, y)
			else:
				return 1
		return 0


class DS:

	def __init__(self, n):
		self.parents = [0] * n
		self.sizes = [0] * n
		for i in range(n):
			self.parents[i] = i
			self.sizes[i] = 1

	def find(self, u):
		if self.parents[u] == u:
			return u
		else:
			self.parents[u] = self.find(self.parents[u])
			return self.parents[u]

	def union(self, u, v):
		rootu = self.find(u)
		rootv = self.find(v)
		if rootu == rootv:
			return
		if self.sizes[rootu] > self.sizes[rootv]:
			self.parents[rootv] = rootu
			self.sizes[rootu] += self.sizes[rootv]
		elif self.sizes[rootu] < self.sizes[rootv]:
			self.parents[rootu] = rootv
			self.sizes[rootv] += self.sizes[rootu]
		else:
			self.parents[rootv] = rootu
			self.sizes[rootu] += self.sizes[rootv]

class Solution:

	def detectCycle(self, V, adj):
		ds = DS(V)
		for u in range(V):
			for v in adj[u]:
				rootu = ds.find(u)
				rootv = ds.find(v)
				if rootu == rootv and u != rootu and (v != rootv):
					return 1
				ds.union(rootu, rootv)
		return 0


from collections import defaultdict

class Solution:

	def detectCycle(self, V, adj):
		parent = [i for i in range(V)]
		rank = [0 for i in range(V)]

		def find(node):
			if node == parent[node]:
				return node
			parent[node] = find(parent[node])
			return parent[node]

		def union(u, v):
			up = find(u)
			vp = find(v)
			if up == vp:
				return
			if rank[up] > rank[vp]:
				parent[vp] = up
			if rank[up] < rank[vp]:
				parent[up] = vp
			else:
				parent[vp] = up
				rank[up] += 1
		for (k, v) in enumerate(adj):
			for j in v:
				if find(k) == find(j) and k < j:
					return 1
				else:
					union(k, j)
		return 0


class Solution:

	def detectCycle(self, V, adj):
		par = [i for i in range(V)]
		rank = [0 for i in range(V)]

		def find(p):
			if p == par[p]:
				return p
			par[p] = find(par[p])
			return par[p]

		def union(u, v):
			up = find(u)
			vp = find(v)
			if up == vp:
				return
			if rank[up] > rank[vp]:
				par[vp] = up
			if rank[up] < rank[vp]:
				par[up] = vp
			else:
				par[vp] = up
				rank[up] += 1
		for (k, v) in enumerate(adj):
			for j in v:
				if find(k) == find(j) and k < j:
					return 1
				else:
					union(k, j)
		return 0


class DSU:

	def __init__(self, n):
		self.rank = [0] * n
		self.parent = [i for i in range(n)]

	def findParent(self, u):
		if u == self.parent[u]:
			return u
		return self.findParent(self.parent[u])

	def unionRank(self, u, v):
		up = self.findParent(u)
		vp = self.findParent(v)
		if up == vp:
			return
		if self.rank[up] < self.rank[vp]:
			self.parent[up] = vp
		elif self.parent[vp] < self.parent[up]:
			self.parent[vp] = up
		else:
			self.parent[vp] = up
			self.rank[up] += 1

class Solution:

	def detectCycle(self, V, adj):
		ds = DSU(V + 1)
		for i in range(V):
			for it in adj[i]:
				if ds.parent[i] == ds.parent[it] and i < it:
					return 1
				else:
					ds.unionRank(i, it)
		return 0


from collections import defaultdict

class Solution:

	def detectCycle(self, V, adj):
		if V <= 2:
			return 0
		parent = [0] * V
		for i in range(V):
			parent[i] = i
		for i in range(V):
			for j in adj[i]:
				x = self.find_parent(parent, i)
				y = self.find_parent(parent, j)
				if x == y:
					return 1
				self.union(parent, x, y)
		return 0

	def find_parent(self, parent, i):
		if parent[i] == i:
			return i
		else:
			return self.find_parent(parent, parent[i])

	def union(self, parent, x, y):
		parent[x] = y


class DS:

	def __init__(self, n):
		self.parents = [0] * n
		self.ranks = [0] * n
		for i in range(n):
			self.parents[i] = i

	def find(self, u):
		if self.parents[u] == u:
			return u
		else:
			self.parents[u] = self.find(self.parents[u])
			return self.parents[u]

	def union(self, u, v):
		if self.ranks[u] > self.ranks[v]:
			self.parents[v] = u
		elif self.ranks[u] < self.ranks[v]:
			self.parents[u] = v
		else:
			self.parents[v] = u
			self.ranks[u] += 1

class Solution:

	def detectCycle(self, V, adj):
		ds = DS(V)
		st = set()
		for u in range(V):
			for v in adj[u]:
				if (v, u) not in st:
					rootu = ds.find(u)
					rootv = ds.find(v)
					if rootu == rootv:
						return 1
					ds.union(rootu, rootv)
					st.add((u, v))
		return 0


from collections import defaultdict
from copy import copy
import sys
sys.setrecursionlimit(10 ** 6)

class Solution:

	def __dfs(self, root, v, adj, count):
		self.visited[v] = True
		ret_val = False
		for u in adj[v]:
			if u == root and count > 1:
				ret_val = True
				break
			if not self.visited[u]:
				ret_val = ret_val or self.__dfs(root, u, adj, count + 1)
		return ret_val

	def detectCycle(self, V, adj):
		ret_val = 0
		for v in range(V):
			self.visited = defaultdict(lambda : False)
			if self.__dfs(v, v, adj, 0):
				ret_val = 1
				break
		return ret_val


class Solution:

	def detectCycle(self, V, adj):

		def find(a, dsu):
			if dsu[a] == -1:
				return a
			else:
				return find(dsu[a], dsu)

		def union(a, b, dsu):
			dsu[a] = b
		dsu = [-1] * V
		visited = set()
		for src in range(V):
			endpoints = adj[src]
			for dest in endpoints:
				if dest in visited:
					continue
				a = find(src, dsu)
				b = find(dest, dsu)
				if a == b:
					return 1
				union(a, b, dsu)
			visited.add(src)
		return 0