Given a maze with N cells. Each cell may have multiple entry points but not more than one exit(i.e entry/exit points are unidirectional doors like valves).
You are given an array Edge[] of N integers, where Edge[i] contains the cell number that can be reached from of cell i in one step. Edge[i] is -1 if the ith cell doesn't have an exit. 
The task is to find the largest sum of a cycle in the maze(Sum of a cycle is the sum of the cell indexes of all cells present in that cycle).
Note:The cells are named with an integer value from 0 to N-1. If there is no cycle in the graph then return -1.
Example 1:
Input:
N = 4
Edge[] = {1, 2, 0, -1}
Output: 3
Explanation: 
There is only one cycle in the graph.
(i.e 0->1->2->0)
Sum of the cell index in that cycle 
= 0 + 1 + 2 = 3.
Example 2:
Input:
N = 4 
Edge[] = {2, 0, -1, 2}
Output: -1
Explanation:
1 -> 0 -> 2 <- 3
There is no cycle in the graph.
Your task:
You dont need to read input or print anything. Your task is to complete the function largestSumCycle() which takes the integer N denoting the number of cells and the array Edge[] as input parameters and returns the sum of the largest sum cycle in the maze.
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(N)
Constraints:
1 ≤ N ≤ 10^{5}
-1 < Edge[i] < N
Edge[i] != i

Source: geeksforgeeks | Difficulty: MEDIUM_HARD
Tags: Graph algorithms

Data structures

Complete search

Starter code: #User function Template for python3





class Solution():

    def largestSumCycle(self, N, Edge):

        #your code goes here

Solutions:
class Solution:

	def largestSumCycle(self, N, Edge):
		cells = []
		result = 0
		covered = {0}
		for i in range(N):
			cells = [i]
			index = i
			while True:
				if Edge[index] == -1 or Edge[index] < i:
					break
				elif Edge[index] in cells:
					eleindex = cells.index(Edge[index])
					totalSum = sum(cells[eleindex:])
					if totalSum > result:
						result = totalSum
					break
				elif Edge[index] in covered:
					break
				else:
					cells.append(Edge[index])
					index = Edge[index]
					covered.add(index)
		if result == 0:
			return -1
		return result


class Solution:

	def largestSumCycle(self, N, Edge):
		nodes = []
		visited = set()
		for node in range(N):
			cycle = set()
			while node != -1 and (not node in visited):
				cycle.add(node)
				node = Edge[node]
				if node in cycle:
					nodes.append(node)
					break
			visited.update(cycle)
		maxi = -1
		for item in nodes:
			summa = item
			node = Edge[item]
			while node != item:
				summa += node
				node = Edge[node]
			maxi = max(maxi, summa)
		return maxi


class Solution:

	def largestSumCycle(self, N, Edge):
		visited = [False] * N
		max_cycle_sum = -1
		path = dict()
		path_keys = []
		for u in range(N):
			if visited[u]:
				continue
			while -1 < u < N:
				if u in path:
					start = path[u]
					cycle_sum = sum(path_keys[start:])
					max_cycle_sum = max(max_cycle_sum, cycle_sum)
					break
				if visited[u]:
					break
				visited[u] = True
				path[u] = len(path_keys)
				path_keys.append(u)
				u = Edge[u]
			path.clear()
		return max_cycle_sum


class Solution:

	def largestSumCycle(self, N, Edge):
		visit = [0] * N
		ans = [-1] * 1
		mp = {}

		def fun(i, se):
			q = []
			visit[i] = 1
			q.append(i)
			s = 0
			while q:
				p = q.pop()
				se.add(p)
				s += p
				mp[p] = s
				if Edge[p] == p:
					ans[0] = max(ans[0], p)
					visit[p] = 1
					continue
				if Edge[p] != -1 and visit[Edge[p]] == 0:
					visit[Edge[p]] = 1
					q.append(Edge[p])
				elif Edge[p] != -1 and visit[Edge[p]] == 1 and (Edge[p] in se):
					s -= mp[Edge[p]] - Edge[p]
					ans[0] = max(ans[0], s)
		for i in range(N):
			if visit[i] == 0 and Edge[i] != -1:
				se = set()
				fun(i, se)
		return ans[0]


import sys
sys.setrecursionlimit(10 ** 6)

class Solution:

	def largestSumCycle(self, N, Edge):

		def dfs(v, path={}, sums=0):
			nonlocal ans, visited, Edge
			if v in visited or Edge[v] == -1:
				return
			if v in path:
				ans = max(ans, sums - path[v])
				return
			path[v] = sums
			dfs(Edge[v], path, sums + v)
			visited.add(v)
		visited = set()
		ans = -1
		for v in range(N):
			dfs(v)
		return ans


import sys
sys.setrecursionlimit(10 ** 6)

class Solution:

	def dfs(self, graph, visited, u):
		if visited[u] == 2:
			return -1
		elif visited[u] == 1:
			(res, cur) = (u, u)
			while graph[cur] != u:
				cur = graph[cur]
				res += cur
			return res
		elif graph[u] != -1:
			visited[u] = 1
			res = self.dfs(graph, visited, graph[u])
			visited[u] = 2
			return res
		else:
			visited[u] = 2
			return -1

	def largestSumCycle(self, N, Edge):
		visited = [0] * N
		res = -1
		for u in range(N):
			res = max(res, self.dfs(Edge, visited, u))
		return res


import sys
sys.setrecursionlimit(10 ** 6)

class Solution:

	def dfs(self, node, p=-1):
		self.vis[node] = 1
		self.par[node] = p
		self.tmp.append(node)
		for i in self.v[node]:
			if self.vis[i] == 0:
				z = self.dfs(i, node)
				if z != -1:
					return z
			elif self.vis[i] == 1:
				sum = i
				while node != i:
					sum += node
					node = self.par[node]
				if node == i:
					return sum
				return -1
		return -1

	def largestSumCycle(self, N, Edge):
		ans = -1
		self.vis = [0] * N
		self.v = [[] for i in range(N)]
		self.par = [0] * N
		self.tmp = []
		for i in range(N):
			if Edge[i] != -1:
				self.v[i].append(Edge[i])
		for i in range(N):
			if ~self.vis[i]:
				ans = max(ans, self.dfs(i))
				for j in self.tmp:
					self.vis[j] = 2
				self.tmp.clear()
		return ans


class Solution:

	def largestSumCycle(self, N, Edge):
		seen = {}
		for (i, e) in enumerate(Edge):
			if e == -1:
				seen[i] = -1
			else:
				seen[i] = 0

		def dfs(node):
			cycle_sum = 0
			cycle_set = {}
			while node != -1 and node not in cycle_set and (seen[node] == 0):
				cycle_sum += node
				cycle_set[node] = [cycle_sum, Edge[node]]
				node = Edge[node]
			cycle_sum += node
			if node in cycle_set:
				cycle_sum -= cycle_set[node][0]
				for (i, next_node) in cycle_set.items():
					seen[next_node[1]] = cycle_sum
				return cycle_sum
			if seen[node] > 0:
				for (i, next_node) in cycle_set.items():
					seen[next_node[1]] = seen[node]
				return seen[node]
			return -1
		ans = -1
		for (i, e) in enumerate(Edge):
			if seen[i] == 0:
				ans = max(ans, dfs(i))
		return ans


from collections import deque
from collections import deque

class Solution:

	def largestSumCycle(self, N, Edge):
		visit = [0] * N
		ans = [-1] * 1
		mp = {}

		def fun(i, se):
			q = deque()
			visit[i] = 1
			q.append(i)
			s = 0
			while q:
				p = q.popleft()
				se.add(p)
				s += p
				mp[p] = s
				if Edge[p] == p:
					ans[0] = max(ans[0], p)
					visit[p] = 1
					continue
				if Edge[p] != -1 and visit[Edge[p]] == 0:
					visit[Edge[p]] = 1
					q.append(Edge[p])
				elif Edge[p] != -1 and visit[Edge[p]] == 1 and (Edge[p] in se):
					s -= mp[Edge[p]] - Edge[p]
					ans[0] = max(ans[0], s)
		for i in range(N):
			if visit[i] == 0 and Edge[i] != -1:
				se = set()
				fun(i, se)
		return ans[0]


import sys
sys.setrecursionlimit(10 ** 8)

class Solution:

	def dfs(self, graph, s, cost, localV, globalV):
		if s in globalV:
			return -1
		if s in localV:
			return cost - localV[s]
		localV[s] = cost
		res = -1
		if graph[s] != -1:
			d = graph[s]
			res = max(res, self.dfs(graph, d, cost + d, localV, globalV))
		return res

	def largestSumCycle(self, N, Edge):
		res = -1
		globalV = set()
		for s in range(N):
			localV = {}
			cost = self.dfs(Edge, s, s, localV, globalV)
			res = max(res, cost)
			globalV.update(set(localV))
		return res


import sys
sys.setrecursionlimit(1000000)

class Solution:

	def __init__(self):
		self.answer = -1

	def searchCycle(self, current_node, visit_list, cycle_visit_list, edge):
		visit_list[current_node] = True
		cycle_visit_list[current_node] = True
		adj_node = edge[current_node]
		if adj_node != -1:
			if visit_list[adj_node] is False:
				self.searchCycle(adj_node, visit_list, cycle_visit_list, edge)
			elif cycle_visit_list[adj_node] is True:
				sum = 0
				curr_tmp_node = adj_node
				while current_node != curr_tmp_node:
					sum += curr_tmp_node
					curr_tmp_node = edge[curr_tmp_node]
				if current_node == curr_tmp_node:
					sum += curr_tmp_node
					self.answer = max(self.answer, sum)
		cycle_visit_list[current_node] = False

	def largestSumCycle(self, N, Edge):
		visit_list = [False] * (N + 2)
		cycle_visit_list = [False] * (N + 2)
		for i in range(N):
			if visit_list[i] is False:
				self.searchCycle(i, visit_list, cycle_visit_list, Edge)
		return self.answer


import sys
sys.setrecursionlimit(10 ** 6)

class Solution:

	def largestSumCycle(self, N, Edge):
		visited = [0] * N
		sc = -1
		for i in range(N):
			sc = max(sc, self.nodes(Edge, visited, i))
		return sc

	def nodes(self, Edge, visited, i):
		if visited[i] == 2:
			return -1
		elif visited[i] == 1:
			sc = i
			current = i
			while Edge[current] != i:
				current = Edge[current]
				sc = sc + current
			return sc
		elif Edge[i] != -1:
			visited[i] = 1
			sc = self.nodes(Edge, visited, Edge[i])
			visited[i] = 2
			return sc
		else:
			visited[i] = 2
			return -1


class Solution:

	def largestSumCycle(self, N, Edge):
		ans = -1
		vis = [-1] * N
		S = [0] * N
		label = 0
		for (i, x) in enumerate(Edge):
			j = i
			s = 0
			while vis[j] == -1:
				vis[j] = label
				S[j] = s
				s += j
				k = Edge[j]
				if 0 <= k < N and vis[k] == label:
					ans = max(ans, s - S[k])
					break
				else:
					j = k
				if j < 0 or j >= N:
					break
			label += 1
		return ans


class Solution:

	def largestSumCycle(self, N, Edge):
		visited = [-1] * N
		res = -1
		for i in range(N):
			j = i
			mn = {}
			sm = 0
			while visited[j] == -1:
				mn[j] = sm
				sm += j
				visited[j] = 1
				j = Edge[j]
				if j == -1:
					break
				if j in mn:
					res = max(res, sm - mn[j])
					break
		return res


import sys
sys.setrecursionlimit(10 ** 6)

class Solution:

	def largestSumCycle(self, N, Edge):
		PointScore = [-1] * len(Edge)
		points = set([i for i in range(N)])
		maxscore = [-1]

		def Walker(point, score):
			if point in points:
				points.remove(point)
			if PointScore[point] == -1:
				PointScore[point] = score
				newPoint = Edge[point]
				if newPoint != -1:
					Walker(newPoint, score + newPoint)
				PointScore[point] = -2
			elif PointScore[point] != -2:
				maxscore[0] = max(maxscore[0], score - PointScore[point])
		while len(points):
			Walker(points.pop(), 0)
		return maxscore[0]


import sys
sys.setrecursionlimit(10 ** 6)

class Solution:

	def largestSumCycle(self, N, Edge):
		adjlist = [[] for i in range(N)]
		for i in range(len(Edge)):
			if Edge[i] != -1:
				adjlist[i].append(Edge[i])
		visitedarr = [False for i in range(N)]
		ans = 0
		for i in range(N):
			if visitedarr[i] == False:
				ancestors = set()
				stack = []
				tempans = self.Helper(adjlist, i, visitedarr, ancestors, stack)
				ans = max(ans, tempans)
		if ans:
			return ans
		return -1

	def Helper(self, adjlist, currentnode, visitedarr, ancestors, stack):
		t = 0
		for x in adjlist[currentnode]:
			if visitedarr[x] == True and x in ancestors:
				te = currentnode
				for idx in range(-1, -len(stack) - 1, -1):
					if stack[idx] == x:
						te += x
						break
					te += stack[idx]
				return te
			elif visitedarr[x] == False:
				ancestors.add(currentnode)
				visitedarr[currentnode] = True
				stack.append(currentnode)
				temp = self.Helper(adjlist, x, visitedarr, ancestors, stack)
				t = max(t, temp)
				stack.pop()
				ancestors.remove(currentnode)
		return t


import sys
sys.setrecursionlimit(10 ** 7)

class Solution:

	def largestSumCycle(self, N, Edge):

		def getsum(node):
			visited = [False for i in range(N)]
			s = node
			visited[node] = True
			temp = Edge[node]
			while visited[temp] != True:
				s += temp
				visited[temp] = True
				temp = Edge[temp]
			return s

		def detect(node, found):
			if found[0] != -2:
				return
			vis[node] = True
			path[node] = True
			nextnode = Edge[node]
			if nextnode != -1:
				if vis[nextnode] == False:
					detect(nextnode, found)
				elif path[nextnode] == True and vis[nextnode] == True:
					found[0] = nextnode
			path[node] = False
		vis = [False for i in range(0, N)]
		path = [False for i in range(0, N)]
		ans = -1
		found = [-2]
		for node in range(0, N):
			if vis[node] == False:
				detect(node, found)
				if found[0] != -2:
					s = getsum(found[0])
					ans = max(ans, s)
					found[0] = -2
		return ans


import sys
sys.setrecursionlimit(150000)

class Solution:

	def largestSumCycle(self, N, Edge):
		visited = [False] * N
		dp_sum = [-1] * N
		ans = [-1]

		def dfs_u(src, cur_sum):
			if dp_sum[src] != -1:
				ans[0] = max(ans[0], cur_sum - dp_sum[src] + src)
				return
			if visited[src]:
				return
			visited[src] = True
			dp_sum[src] = cur_sum + src
			if Edge[src] != -1:
				dfs_u(Edge[src], cur_sum + src)
			dp_sum[src] = -1
		for i in range(N):
			if not visited[i]:
				dfs_u(i, 0)
		return ans[0]


import sys
sys.setrecursionlimit(int(1000000.0))
from functools import lru_cache

class Solution:

	def largestSumCycle(self, N, Edge):
		vis = [0] * N
		sm = [0] * N

		def soln(i, res):
			if vis[i] == 1:
				soln.res = max(soln.res, res - sm[i])
				return
			if Edge[i] == -1 or vis[i] == 2:
				return float('-inf')
			vis[i] = 1
			sm[i] = res
			soln(Edge[i], i + res)
			sm[i] = 0
			vis[i] = 2
			return res
		soln.res = float('-inf')
		for i in range(N):
			soln(i, 0)
		res = soln.res
		return res if res != float('-inf') else -1


import sys
sys.setrecursionlimit(10 ** 6)

class Solution:

	def largestSumCycle(self, N, Edge):
		dp = [0 for i in range(N)]
		cx = [0 for i in range(N)]
		solve = [-1]

		def dfs(n, s, c):
			cx[n] = c
			dp[n] = s
			s += n
			if Edge[n] != -1:
				w = Edge[n]
				if cx[w]:
					if cx[w] == c:
						solve[0] = max(solve[0], s - dp[w])
				else:
					dfs(w, s, c)
		c = 1
		for i in range(N):
			if not cx[i]:
				dfs(i, 0, c)
				c += 1
		return solve[0]


import sys
sys.setrecursionlimit(10 ** 6)

class Solution:

	def dfs(self, graph, visited, u):
		if visited[u] == 2:
			return -1
		elif visited[u] == 1:
			(res, cur) = (u, u)
			while graph[cur] != u:
				cur = graph[cur]
				res += cur
			return res
		elif graph[u] != -1:
			visited[u] = 1
			res = self.dfs(graph, visited, graph[u])
			visited[u] = 2
			return res
		else:
			visited[u] = 2
			return -1

	def largestSumCycle(self, N, Edge):
		visited = [0] * N
		res = -1
		for u in range(N):
			res = max(res, self.dfs(Edge, visited, u))
		return res
if __name__ == '__main__':
	for _ in range(int(input())):
		N = int(input())
		Edge = [int(i) for i in input().split()]
		print(Solution().largestSumCycle(N, Edge))


class Solution:

	def largestSumCycle(self, N, edge):
		vis = [-1] * N
		dp_arr = [0] * N
		res = -1
		for i in range(N):
			if vis[i] == -1:
				(temp, val, stack) = (i, 0, [])
				while True:
					vis[temp] = 0
					dp_arr[temp] = val
					stack.append(temp)
					if edge[temp] != -1:
						if vis[edge[temp]] == -1:
							val += temp
							temp = edge[temp]
						elif vis[edge[temp]] == 0:
							res = max(temp + val - dp_arr[edge[temp]], res)
							break
						else:
							break
					else:
						break
				while stack:
					vis[stack.pop()] = 1
		return res


class Solution:

	def largestSumCycle(self, N, Edge):
		check = [0] * N
		ans = -1
		for i in range(N):
			if Edge[i] != -1 and check[i] == 0:
				check[i] = 1
				a = {i: 0}
				s = i
				curr = Edge[i]
				while curr not in a and (not check[curr]):
					a[curr] = s
					s += curr
					check[curr] = 1
					curr = Edge[curr]
					if curr == -1:
						break
				if curr in a:
					ans = max(ans, s - a[curr])
		return ans


class Solution:

	def largestSumCycle(self, N, Edge):
		visited = [0 for i in range(N)]
		ans = -1
		s = 0
		cur = 0
		cycle = False
		for i in range(N):
			cur = i
			s = 0
			cycle = 0
			while cur != -1:
				if visited[cur] != 0:
					cycle = 1 if visited[cur] == i + 1 else 0
					break
				visited[cur] = i + 1
				cur = Edge[cur]
			if cycle:
				s = cur
				savecur = cur
				cur = Edge[cur]
				while cur != savecur:
					s += cur
					cur = Edge[cur]
				ans = max(ans, s)
		return ans


class Solution:

	def solve(self, p, Edge):
		su = p
		s = p
		p = Edge[s]
		while p != s:
			su += p
			p = Edge[p]
		return su

	def largestSumCycle(self, N, Edge):
		visited = [False for i in range(N)]
		answer = 0
		for i in range(len(Edge)):
			if not visited[i]:
				mp = {}
				visited[i] = True
				mp[i] = 0
				p = Edge[i]
				flag = True
				while p not in mp.keys():
					if p == -1 or visited[p]:
						flag = False
						break
					visited[p] = True
					mp[p] = 0
					p = Edge[p]
				if flag:
					answer = max(self.solve(p, Edge), answer)
		if answer == 0:
			return -1
		return answer


class Solution:

	def largestSumCycle(self, N, Edge):
		visited = [False for i in range(N)]
		ans = -1
		for i in range(N):
			if not visited[i] and Edge[i] != -1:
				(sum, v) = (i, Edge[i])
				result = {}
				while Edge[v] != -1 and (not visited[v]):
					visited[v] = True
					result[v] = sum
					sum += v
					v = Edge[v]
				if v in result:
					sum -= result[v]
					ans = max(ans, sum)
		return ans


class Solution:

	def largestSumCycle(self, N, Edge):
		done = set()
		ans = -1
		for i in range(N):
			if i in done:
				continue
			path = [i]
			d2 = set([i])
			x = i
			cycle = False
			done.add(i)
			while True:
				x = Edge[x]
				if x == -1:
					break
				if x in d2:
					cycle = True
					break
				if x in done:
					break
				path.append(x)
				done.add(x)
				d2.add(x)
			if cycle:
				s = 0
				while path:
					y = path.pop()
					s += y
					if y == x:
						break
				ans = max(ans, s)
		return ans


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

class Solution:

	def dfs(self, graph, vertex, visited, path, curr_p=-1):
		visited[vertex] = 1
		path[vertex] = curr_p
		self.temp.append(vertex)
		for i in graph[vertex]:
			if not visited[i]:
				sum_ = self.dfs(graph, i, visited, path, vertex)
				if sum_ != -1:
					return sum_
			elif visited[i] == 1:
				sum_a = i
				while vertex != i:
					sum_a += vertex
					vertex = path[vertex]
				if vertex == i:
					return sum_a
				return -1
		return -1

	def largestSumCycle(self, N, Edge):
		graph = defaultdict(list)
		for i in range(N):
			if Edge[i] != -1:
				graph[i].append(Edge[i])
		cnt = -1
		visited = [0] * N
		path = [0] * N
		self.temp = []
		for i in range(N):
			if not visited[i]:
				flag_s = self.dfs(graph, i, visited, path, -1)
				cnt = max(cnt, flag_s)
				for j in self.temp:
					visited[j] = 2
				self.temp.clear()
		return cnt


from typing import List
import math
import sys
sys.setrecursionlimit(10 ** 6)

class Solution:

	def dfs(self, adj, node, par):
		self.vis[node] = 1
		self.parent[node] = par
		self.temp.append(node)
		for child in adj[node]:
			if self.vis[child] == 0:
				cycle = self.dfs(adj, child, node)
				if cycle != -1:
					return cycle
			elif self.vis[child] == 1:
				sum = child
				while node != child:
					sum += node
					node = self.parent[node]
				return sum
		return -1

	def largestSumCycle(self, N: int, Edge: List[int]) -> int:
		self.vis = [0 for i in range(N)]
		self.parent = [-1 for i in range(N)]
		self.temp = []
		adj = [[] for i in range(N)]
		for i in range(N):
			if Edge[i] != -1:
				adj[i].append(Edge[i])
		ans = -math.inf
		for i in range(N):
			if self.vis[i] == 0:
				ans = max(ans, self.dfs(adj, i, -1))
				for nd in self.temp:
					self.vis[nd] = 2
				self.temp.clear()
		return ans


class Solution:

	def largestSumCycle(self, N, Edge):
		OFFSET = 1
		sums = [-1] * N
		result = -1
		for i0 in range(N):
			if sums[i0] >= 0:
				continue
			sums[i0] = OFFSET
			csum = OFFSET + i0
			i = Edge[i0]
			i1 = i0
			while i >= 0 and sums[i] < 0:
				i1 = i
				sums[i] = csum
				csum += i
				i = Edge[i]
			if i >= 0 and sums[i] >= OFFSET:
				result = max(result, csum - sums[i])
			else:
				pass
			i = i0
			while sums[i] > 0:
				sums[i] = 0
				i = Edge[i]
		return result


import sys
sys.setrecursionlimit(10 ** 6)

class Solution:

	def dfs(self, Edge, i, vis, pathV, ans):
		vis[i] = True
		pathV[i] = True
		if Edge[i] != -1:
			next = Edge[i]
			if not vis[next]:
				self.dfs(Edge, next, vis, pathV, ans)
			elif pathV[next]:
				res = next
				node = Edge[next]
				while node != next:
					res += node
					node = Edge[node]
				ans[0] = max(ans[0], res)
		pathV[i] = False

	def largestSumCycle(self, N, Edge):
		vis = [False] * N
		pathV = [False] * N
		ans = [-1]
		for i in range(N):
			if not vis[i]:
				self.dfs(Edge, i, vis, pathV, ans)
		return ans[0]