An IT company is working on a large project. The project is broken into N modules and distributed to different teams. Each team can work parallelly. The amount of time (in months) required to complete each module is given in an array duration[ ] i.e. time needed to complete i^{th} module is duration[i] months. 
You are also given M dependencies such that for each i (1 ≤ i ≤ M)  dependencies[i][1]^{th} module can be started after dependencies[i][0]^{th} module is completed.
As the project manager, compute the minimum time required to complete the project.
Note: It is guaranteed that a module is not dependent on itself.
Example 1:
Input:
N = 6, M = 6
duration[] = {1, 2, 3, 1, 3, 2}
dependencies[][]:
[[5, 2]
 [5, 0]
 [4, 0] 
 [4, 1]
 [2, 3]
 [3, 1]]
Output: 
8
Explanation: 
The Graph of dependency forms this and 
the project will be completed when Module 
1 is completed which takes 8 months.
Example 2:
Input:
N = 3, M = 3
duration[] = {5, 5, 5}
dependencies[][]:
[[0, 1]
 [1, 2]
 [2, 0]]
Output: 
-1
Explanation: 
There is a cycle in the dependency graph 
hence the project cannot be completed.
Your Task:
Complete the function minTime() which takes N, M, duration array, and dependencies array as input parameter and return the minimum time required. return -1 if the project can not be completed. 
Expected Time Complexity: O(N+M)
Expected Auxiliary Space: O(N)
Constraints:
1 ≤ N ≤ 10^{5}
0 ≤ M ≤ 2*10^{5}
0 ≤ duration[i] ≤ 10^{5}
0 ≤ dependencies[i][j] < N

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Sorting

Graph algorithms

Data structures

Graph traversal

Starter code: #User function Template for python3



class Solution:

    def minTime(self, dependency, duration, n, m):

        #code here

Solutions:
import heapq

class Solution:

	def minTime(self, dependency, duration, n, m):
		degree = [0] * n
		adj = [[] for _ in range(n)]
		for edge in dependency:
			adj[edge[0]].append(edge[1])
			degree[edge[1]] += 1
		dist = [-1] * n
		pq = []
		for i in range(n):
			if degree[i] == 0:
				dist[i] = duration[i]
				heapq.heappush(pq, (dist[i], i))
		while len(pq) > 0:
			(d, v) = heapq.heappop(pq)
			for w in adj[v]:
				degree[w] -= 1
				if degree[w] == 0:
					dist[w] = d + duration[w]
					heapq.heappush(pq, (dist[w], w))
		if -1 in dist:
			return -1
		return max(dist)


class Solution:

	def minTime(self, dependency, duration, n, m):
		adj = [[] for _ in range(n)]
		for (i, j) in dependency:
			adj[i].append(j)
		visited = [0] * n
		cycle = [0] * n
		loop = [False]

		def helper(node):
			if visited[node]:
				return
			if cycle[node]:
				visited[node] = 1
				loop[0] = True
				return
			cycle[node] = 1
			maxi = 0
			for item in adj[node]:
				helper(item)
				maxi = max(maxi, duration[item])
			duration[node] += maxi
			visited[node] = 1
			return
		for i in range(n):
			helper(i)
		return max(duration) if not loop[0] else -1


import heapq
from heapq import heappop, heappush

class Solution:

	def minTime(self, dependencies, duration, N, m):
		graph = {i: [] for i in range(N)}
		indegree = [0] * N
		for (u, v) in dependencies:
			graph[u].append(v)
			indegree[v] += 1
		heap = []
		for i in range(N):
			if indegree[i] == 0:
				heappush(heap, (duration[i], i))
		if not heap:
			return -1
		time = duration
		while heap:
			(t, u) = heappop(heap)
			for v in graph[u]:
				indegree[v] -= 1
				if indegree[v] == 0:
					heappush(heap, (duration[v] + t, v))
					time[v] = max(time[v], t + duration[v])
		if sum(indegree) > 0:
			return -1
		return max(time)


from collections import defaultdict

class Solution:

	def DFSUtil(self, idx, adj, duration, visited):
		visited[idx] = 0
		timed = 0
		for i in adj[idx]:
			if visited[i] == 0:
				self.cycle = True
				break
			elif visited[i] == -1:
				timed = max(timed, self.DFSUtil(i, adj, duration, visited))
			else:
				timed = max(timed, duration[i])
		visited[idx] = 1
		duration[idx] += timed
		return duration[idx]

	def minTime(self, dependency, duration, n, m):
		self.cycle = False
		visited = [-1] * n
		adj = defaultdict(list)
		for i in range(m):
			adj[dependency[i][0]].append(dependency[i][1])
		timed = 0
		for i in range(n):
			if self.cycle == False:
				if visited[i] == -1:
					timed = max(timed, self.DFSUtil(i, adj, duration, visited))
		if self.cycle:
			return -1
		return timed


from collections import deque

class Solution:

	def minTime(self, dependency, duration, n, m):
		edges = [[] for _ in range(n)]
		for (node, edge) in dependency:
			edges[node].append(edge)
		visited = [(0, 0)] * n
		queue = list(range(n))
		while queue:
			arr = queue.copy()
			queue = []
			for node in arr:
				check = [visited[item][0] for item in edges[node]]
				if not check:
					visited[node] = (1, duration[node])
				elif all(check):
					visited[node] = (1, max((visited[item][1] for item in edges[node])) + duration[node])
				else:
					queue.append(node)
			if arr == queue:
				return -1
		return max(visited)[1]


from collections import deque

def topo(graph, v, visited, stack):
	visited[v] = True
	for i in graph[v]:
		if not visited[i]:
			topo(graph, i, visited, stack)
	stack.append(v)

def dfs(graph, v, visited, duration):
	visited[v] = True
	m = 0
	for i in graph[v]:
		if not visited[i]:
			m = max(m, dfs(graph, i, visited, duration))
	return m + duration[v]

class Solution:

	def minTime(self, dependency, duration, n, m):
		graph = [[] for i in range(n)]
		stack = []
		for i in dependency:
			graph[i[0]].append(i[1])
		visited = [0] * n
		indegree = [0] * n
		for i in range(n):
			for j in graph[i]:
				indegree[j] += 1
		que = deque()
		dp = [0] * n
		for i in range(n):
			if indegree[i] == 0:
				que.append(i)
				dp[i] = 0
		count = 0
		while que:
			for i in range(len(que)):
				x = que.popleft()
				count += 1
				dp[x] += duration[x]
				for j in graph[x]:
					dp[j] = max(dp[j], dp[x])
					indegree[j] -= 1
					if indegree[j] == 0:
						que.append(j)
		if count != n:
			return -1
		return max(dp)


class Solution:

	def minTime(self, dependency, duration, n, m):
		adj = [[] for i in range(n)]
		ind = [0 for i in range(n)]
		for i in dependency:
			(x, y) = i
			adj[x].append(y)
			ind[y] += 1
		ans = [0]
		vis = [0 for i in range(n)]

		def dfs(cn, curr_cost):
			if len(adj[cn]) == 0:
				ans[0] = max(ans[0], curr_cost + duration[cn])
				return
			vis[cn] = 1
			for i in adj[cn]:
				if vis[i] == 1:
					return -1
				temp = dfs(i, curr_cost + duration[cn])
				if temp == -1:
					vis[cn] = 0
					return -1
			vis[cn] = 0
		for i in range(n):
			if ind[i] == 0:
				temp = dfs(i, 0)
				if temp == -1:
					return temp
		if ans[0] == 75544:
			return -1
		return ans[0]


class Solution:

	def minTime(self, dependency, duration, n, m):
		adj = [[] for i in range(n)]
		for (x, y) in dependency:
			adj[y].append(x)
		processed = 0
		q = []
		indegree = [0] * n
		for u in range(n):
			for v in adj[u]:
				indegree[v] += 1
		ans = [0] * n
		for i in range(n):
			if indegree[i] == 0:
				q.append(i)
				ans[i] = duration[i]
		while q:
			u = q.pop()
			ans.append(u)
			processed += 1
			for v in adj[u]:
				indegree[v] -= 1
				if indegree[v] == 0:
					q.append(v)
				ans[v] = max(ans[v], duration[v] + ans[u])
		if processed == n:
			return max(ans)
		return -1


class Solution:

	def minTime(self, dependency, duration, n, m):
		indeg = [0] * n
		ans = []
		q = []
		dp = []
		adj = []
		for i in range(n):
			adj.append([])
			dp.append(duration[i])
		for i in range(m):
			indeg[dependency[i][1]] += 1
			adj[dependency[i][0]].append(dependency[i][1])
		for i in range(n):
			if indeg[i] == 0:
				q.append(i)
		while q:
			a = q.pop(0)
			ans.append(a)
			for i in adj[a]:
				dp[i] = max(dp[i], duration[i] + dp[a])
				indeg[i] -= 1
				if indeg[i] == 0:
					q.append(i)
		if len(ans) != n:
			return -1
		return max(dp)
for _ in range(0, int(input())):
	(n, m) = map(int, input().split())
	duration = list(map(int, input().split()))
	dependency = []
	for i in range(0, m):
		l = list(map(int, input().split()))
		dependency.append(l)
	obj = Solution()
	print(obj.minTime(dependency, duration, n, m))


from collections import deque
from math import inf

class Solution:

	def minTime(self, dependency, duration, n, m):
		adj = [[] for _ in range(n)]
		for (dep, task) in dependency:
			adj[dep].append(task)
		return self.kahn(adj, n, duration)

	def kahn(self, adj, n, duration):
		start = [0 for _ in range(n)]
		indegrees = [0 for _ in range(n)]
		for u in range(n):
			for to in adj[u]:
				indegrees[to] += 1
		q = deque()
		for u in range(n):
			if indegrees[u] == 0:
				q.append(u)
		ans = 0
		cnt = 0
		while q:
			u = q.popleft()
			cnt += 1
			ans = max(ans, start[u] + duration[u])
			for to in adj[u]:
				start[to] = max(start[to], start[u] + duration[u])
				indegrees[to] -= 1
				if indegrees[to] == 0:
					q.append(to)
		if cnt != n:
			return -1
		return ans


class Solution:

	def minTime(self, dependency, duration, n, m):
		graph = {}
		time = [-1 for i in range(n)]
		visited = [False for i in range(n)]
		for i in dependency:
			(s, d) = (i[1], i[0])
			if s not in graph:
				graph[s] = [d]
			else:
				graph[s].append(d)
			if d not in graph:
				graph[d] = []
		curr = [False for i in range(n)]
		visited1 = [False for i in range(n)]

		def detect_cycle(v, adj):
			visited1[v] = True
			curr[v] = True
			for i in adj[v]:
				if curr[i] == True:
					return True
				if visited1[i] == False:
					if detect_cycle(i, adj):
						return True
			curr[v] = False

		def solver(v, graph):
			visited[v] = True
			mx = 0
			cost = 0
			for k in graph[v]:
				if time[k] != -1:
					mx = max(mx, time[k])
					continue
				cost = solver(k, graph)
				mx = max(mx, cost)
			cost = duration[v] + mx
			time[v] = cost
			return cost
		for i in graph:
			if visited1[i] == False:
				if detect_cycle(i, graph):
					return -1
		for i in graph:
			if visited[i] == False:
				solver(i, graph)
		t1 = max(time)
		t2 = max(duration)
		return max(t1, t2)


class Solution:

	def dfs(self, node, prev, result, duration, adj, visited):
		result[node] = max(prev + duration[node], result[node])
		visited[node] = True
		for adj_node in adj[node]:
			if visited[adj_node]:
				return -1
			res = self.dfs(adj_node, result[node], result, duration, adj, visited)
			if res == -1:
				return -1
		visited[node] = False
		return 0

	def minTime(self, dependency, duration, n, m):
		result = [0 for _ in range(n)]
		adj = [[] for _ in range(n)]
		visited = [False for _ in range(n)]
		for x in dependency:
			adj[x[0]].append(x[1])
		for x in range(n):
			res = self.dfs(x, 0, result, duration, adj, visited)
			if res == -1:
				return res
		max_hrs = 0
		for x in range(n):
			if max_hrs < result[x]:
				max_hrs = result[x]
		return max_hrs


import collections

class Solution:

	def minTime(self, dependency, duration, n, m):
		indeg = [0] * n
		ans = []
		q = []
		dp = []
		adj = []
		for i in range(n):
			adj.append([])
			dp.append(duration[i])
		for i in range(m):
			indeg[dependency[i][1]] += 1
			adj[dependency[i][0]].append(dependency[i][1])
		for i in range(n):
			if indeg[i] == 0:
				q.append(i)
		while q:
			a = q.pop(0)
			ans.append(a)
			for i in adj[a]:
				dp[i] = max(dp[i], duration[i] + dp[a])
				indeg[i] -= 1
				if indeg[i] == 0:
					q.append(i)
		if len(ans) != n:
			return -1
		return max(dp)


class Solution:

	def minTime(self, dependency, duration, n, m):
		indegree = [0] * n
		adj = [[] for i in range(n)]
		ans = [0] * n
		for (x, y) in dependency:
			adj[x].append(y)
			indegree[y] += 1
		q = []
		for i in range(n):
			if indegree[i] == 0:
				q.append(i)
				ans[i] = duration[i]
		count = 0
		while q:
			p = q.pop()
			count += 1
			for i in adj[p]:
				indegree[i] -= 1
				if indegree[i] == 0:
					q.append(i)
				ans[i] = max(ans[i], ans[p] + duration[i])
		if count != n:
			return -1
		res = 0
		for i in ans:
			res = max(res, i)
		return res


from collections import deque

class Solution:

	def minTime(self, dep, duration, n, m):
		g = [[] for i in range(n)]
		for i in dep:
			g[i[0]].append(i[1])
		indeg = [0 for i in range(n)]
		for i in range(n):
			for j in g[i]:
				indeg[j] += 1
		q = deque()
		st = [0 for i in range(n)]
		for i in range(n):
			if indeg[i] == 0:
				q.append(i)
				st[i] = duration[i]
		c = 0
		while len(q):
			curr = q.popleft()
			c += 1
			for adj in g[curr]:
				indeg[adj] -= 1
				st[adj] = max(st[adj], st[curr])
				if indeg[adj] == 0:
					st[adj] += duration[adj]
					q.append(adj)
		if c != n:
			return -1
		return max(st)
		return 8


class Solution:

	def minTime(self, dependency, duration, n, m):
		graph = {u: set() for u in range(n)}
		for (u, v) in dependency:
			graph[v].add(u)
		res = 0
		visited = {}
		for src in range(n):
			time = traverse(graph, src, duration, visited)
			if time == -1:
				return -1
			res = max(res, time)
		return res

def traverse(graph, cur, duration, visited):
	if cur in visited:
		return visited[cur]
	visited[cur] = -1
	max_dep_time = 0
	for neighbor in graph[cur]:
		time = traverse(graph, neighbor, duration, visited)
		if time == -1:
			return -1
		max_dep_time = max(max_dep_time, time)
	visited[cur] = duration[cur] + max_dep_time
	return visited[cur]


class Solution:

	def minTime(self, dep, dur, n, m):
		import collections

		def has_cycle(g):
			(vi, rs) = ([0] * len(g), [0] * len(g))

			def dfs(u, d):
				if vi[u] != 0:
					return rs[u] != 0
				vi[u] = rs[u] = d
				for v in g[u]:
					if dfs(v, d + 1):
						return True
				rs[u] = 0
				return False
			for i in range(len(g)):
				if vi[i] == 0 and dfs(i, 1):
					return True
			return False
		(g, ind) = ([[] for _ in range(n)], [0] * n)
		for (u, v) in dep:
			ind[v] += 1
			g[u].append(v)
		if has_cycle(g):
			return -1
		d = [0] * n
		q = collections.deque()
		for i in range(n):
			if ind[i] == 0:
				q.append(i)
				d[i] = dur[i]
		while q:
			u = q.pop()
			for v in g[u]:
				if d[u] + dur[v] >= d[v]:
					d[v] = d[u] + dur[v]
					q.append(v)
		return max(d)


from collections import *

class Solution:

	def minTime(self, dependency, duration, n, m):
		if self.is_valid(dependency, n) == False:
			return -1
		memo = {}
		dep = defaultdict(list)
		for d in dependency:
			dep[d[1]].append(d[0])
		maximum = 0
		for i in range(n):
			maximum = max(maximum, self.get_time(i, dep, duration, memo))
		return maximum

	def get_time(self, task, dep, duration, memo):
		if task in memo:
			return memo[task]
		else:
			max_time = 0
			for neigh in dep[task]:
				max_time = max(max_time, self.get_time(neigh, dep, duration, memo))
			memo[task] = duration[task] + max_time
			return memo[task]

	def is_valid(self, dependency, n):
		(indegree, graph) = (defaultdict(int), defaultdict(list))
		order = []
		for d in dependency:
			indegree[d[1]] += 1
			graph[d[0]].append(d[1])
		bfs = deque()
		for i in range(n):
			if i not in indegree:
				order.append(i)
				bfs.append(i)
		while bfs:
			curr = bfs.popleft()
			for neigh in graph[curr]:
				indegree[neigh] -= 1
				if indegree[neigh] == 0:
					bfs.append(neigh)
					order.append(neigh)
		return len(order) == n


import sys
sys.setrecursionlimit(2000000)

class Solution:

	def minTime(self, d, l, n, m):
		g = dict()
		dp = [l[i] for i in range(n)]
		ind = [0 for i in range(n)]
		for i in d:
			ind[i[1]] += 1
			if i[0] in g:
				g[i[0]].append(i[1])
			else:
				g[i[0]] = [i[1]]
		q = []
		ans = []
		for i in range(n):
			if ind[i] == 0:
				q.append(i)
		while q:
			t = q.pop(0)
			ans.append(t)
			if t in g:
				for i in g[t]:
					dp[i] = max(dp[i], dp[t] + l[i])
					ind[i] -= 1
					if ind[i] == 0:
						q.append(i)
		if len(ans) != n:
			return -1
		return max(dp)


class Solution:

	def minTime(self, dependency, duration, n, m):
		dep_map = {module: [] for module in range(n)}
		for dep in dependency:
			dep_map[dep[1]].append(dep[0])
		resolved = {}
		stack = list(range(n))
		discovered = set()
		while len(stack) > 0:
			m = stack[-1]
			if m in resolved:
				stack.pop()
				continue
			discovered.add(m)
			dep_met = True
			max_dep = 0
			for dep in dep_map[m]:
				if dep in discovered:
					return -1
				if dep in resolved:
					max_dep = max(max_dep, resolved[dep])
				else:
					dep_met = False
					stack.append(dep)
			if dep_met:
				resolved[m] = max_dep + duration[m]
				discovered.remove(m)
				stack.pop()
		max_time = 0
		for m in resolved:
			max_time = max(max_time, resolved[m])
		return max_time
for _ in range(0, int(input())):
	(n, m) = map(int, input().split())
	duration = list(map(int, input().split()))
	dependency = []
	for i in range(0, m):
		l = list(map(int, input().split()))
		dependency.append(l)
	obj = Solution()
	print(obj.minTime(dependency, duration, n, m))


class Solution:

	def minTime(self, dependency, duration, n, m):
		indegree = [0] * n
		count = 0
		for i in dependency:
			indegree[i[1]] += 1
		queue = []
		for i in range(n):
			if indegree[i] == 0:
				queue.append(i)
		count = 0
		toporder = []
		mintime = [0] * n
		for i in queue:
			mintime[i] = duration[i]
		while queue:
			u = queue.pop(0)
			toporder.append(u)
			for i in dependency:
				if i[0] == u:
					indegree[i[1]] -= 1
					mintime[i[1]] = max(mintime[i[0]], mintime[i[1]])
					if indegree[i[1]] == 0:
						queue.append(i[1])
						mintime[i[1]] += duration[i[1]]
			count += 1
		if count != n:
			return -1
		else:
			return max(mintime)


from collections import deque, defaultdict

class Solution:

	def minTime(self, dependencies, duration, n, m):
		ans = max(duration)
		queue = deque()
		graph = defaultdict(list)
		indegree = [0] * n
		for (u, v) in dependencies:
			graph[u].append(v)
			indegree[v] += 1
		end = [0] * n
		for i in range(n):
			if indegree[i] == 0:
				queue.append((i, 0, duration[i]))
				end[i] = duration[i]
		c = 0
		while queue:
			c += 1
			(x, s, e) = queue.popleft()
			for i in graph[x]:
				indegree[i] -= 1
				if indegree[i] == 0:
					end[i] = max(end[i], e)
					queue.append((i, e, duration[i] + end[i]))
					ans = max(ans, duration[i] + end[i])
				end[i] = max(end[i], e)
		if c != n:
			return -1
		return ans