Given a directed graph with N nodes and M edges. A source node and a destination node are also given, we need to find how many edges we need to reverse in order to make at least 1 path from the source node to the destination node.
Note: In case there is no way then return -1.
Example 1:
Input:
N=3
M=2
edges[][]={{1,2},{3,2}}
src=1
dst=3
Output:
1
Explanation:
Reverse the edge 3->2.
Example 2:
Input:
N=4
M=3
edges[][]={{1,2},{2,3},{3,4}}
src=1
dst=4
Output:
0
Explanation;
One path already exists between 1 to 4 it is 1->2->3->4.
 
Your Task:  
You don't need to read input or print anything. Your task is to complete the function minimumEdgeReversal() which takes the edge list edges, N the number of nodes of the graph. src (source), and dst (destination) vertex as input parameters and returns the minimum number of edges to be reversed
Expected Time Complexity: O(M*log(M))
Expected Auxiliary Space: O(N+M)
Constraints:
1 <= N ,M<= 10^{5}
1<=edges[i][0],edges[i][1]<=N

Source: geeksforgeeks | Difficulty: MEDIUM

Starter code: from typing import List





from typing import List





class Solution:

    def minimumEdgeReversal(self,edges : List[List[int]], n : int, m : int, src : int, dst : int) -> int:

        # code here

        



Solutions:
from typing import List
from typing import List
import heapq as h
from collections import defaultdict as dict, deque as dq

class Solution:

	def minimumEdgeReversal(self, edges: List[List[int]], n: int, m: int, src: int, dst: int) -> int:
		adj = dict(list)
		edges = [tuple(edge) for edge in edges]
		edges = set(edges)
		reversedEdges = set()
		for edge in edges:
			if (edge[1], edge[0]) not in edges:
				reversedEdges.add((edge[1], edge[0]))
		for edge in edges:
			adj[edge[0]].append((edge[1], 0))
		for edge in reversedEdges:
			adj[edge[0]].append((edge[1], 1))
		dist = [float('inf') for i in range(n + 1)]
		dist[src] = 0
		pq = [(0, src)]
		h.heapify(pq)
		while pq:
			(nodeDist, node) = h.heappop(pq)
			for (neib, neibDist) in adj[node]:
				if nodeDist + neibDist < dist[neib]:
					dist[neib] = nodeDist + neibDist
					h.heappush(pq, (dist[neib], neib))
		return dist[dst] if dist[dst] != float('inf') else -1


from typing import List
from typing import List
import heapq

class Solution:

	def minimumEdgeReversal(self, edges: List[List[int]], n: int, m: int, src: int, dst: int) -> int:
		g = [[] for _ in range(n + 1)]
		for (u, v) in edges:
			g[u].append((v, 0))
			g[v].append((u, 1))
		dis = [float('inf')] * (n + 1)
		dis[src] = 0
		mnhp = [(0, src)]
		while mnhp:
			(d, u) = heapq.heappop(mnhp)
			if u == dst:
				break
			for (v, w) in g[u]:
				if dis[v] > d + w:
					dis[v] = d + w
					heapq.heappush(mnhp, (dis[v], v))
		return dis[dst] if dis[dst] != float('inf') else -1


from typing import List
from typing import List
import heapq

class Solution:

	def minimumEdgeReversal(self, edges: List[List[int]], n: int, m: int, src: int, dst: int) -> int:
		adj = {}
		for i in range(1, n + 1):
			adj[i] = []
		for edge in edges:
			u = edge[0]
			v = edge[1]
			adj[u].append([v, 0])
			adj[v].append([u, 1])
		(_, d) = self.dijkstra(adj, src, dst)
		if dst in d:
			return d[dst]
		return -1

	def dijkstra(self, adj, start, target):
		d = {start: 0}
		parent = {start: None}
		pq = [(0, start)]
		visited = set()
		while pq:
			(du, u) = heapq.heappop(pq)
			if u in visited:
				continue
			if u == target:
				break
			visited.add(u)
			for (v, weight) in adj[u]:
				if v not in d or d[v] > du + weight:
					d[v] = du + weight
					parent[v] = u
					heapq.heappush(pq, (d[v], v))
		return (parent, d)


from typing import List

class Solution:

	def minimumEdgeReversal(self, edges: List[List[int]], n: int, m: int, src: int, dst: int) -> int:
		from heapq import heappush, heappop
		(INV, src, dst) = (10 ** 9, src - 1, dst - 1)
		adjs = [{} for _ in range(n)]
		for (a, b) in edges:
			(a, b) = (a - 1, b - 1)
			adjs[a][b] = 0
			adjs[b][a] = adjs[b].get(a, 1)
		g = [INV] * n
		g[src] = 0
		H = [(0, src)]
		while H:
			(dnd, nd) = heappop(H)
			if dnd > g[nd]:
				continue
			if nd == dst:
				break
			for (nei, w) in adjs[nd].items():
				if g[nd] + w < g[nei]:
					g[nei] = g[nd] + w
					heappush(H, (g[nd] + w, nei))
		return g[dst] if g[dst] < INV else -1


from typing import List
import heapq

class Solution:

	def minimumEdgeReversal(self, edges: List[List[int]], n: int, m: int, src: int, dst: int) -> int:
		adj = [[] for i in range(n + 1)]
		for (i, j) in edges:
			adj[i].append([j, 0])
			adj[j].append([i, 1])
		dist = [float('infinity')] * (n + 1)
		dist[src] = 0
		q = []
		heapq.heapify(q)
		heapq.heappush(q, (0, src))
		while q:
			(small, node) = heapq.heappop(q)
			for i in adj[node]:
				v = i[0]
				wt = i[1]
				if wt + small < dist[v]:
					dist[v] = wt + small
					heapq.heappush(q, (wt + small, v))
		if dist[dst] == float('infinity'):
			return -1
		return dist[dst]


from typing import List
from collections import defaultdict
import heapq

class Solution:

	def minimumEdgeReversal(self, edges, n, m, src, dst):
		adj = defaultdict(list)
		for edge in edges:
			adj[edge[0]].append([edge[1], 0])
			adj[edge[1]].append([edge[0], 1])
		dist = [10 ** 9] * (n + 1)
		dist[src] = 0
		q = []
		q.append([0, src])
		heapq.heapify(q)
		while q:
			top = heapq.heappop(q)
			min_cost = top[0]
			node = top[1]
			for (ngbhr, cost) in adj[node]:
				if min_cost + cost < dist[ngbhr]:
					dist[ngbhr] = min_cost + cost
					heapq.heappush(q, [min_cost + cost, ngbhr])
		if dist[dst] == 10 ** 9:
			return -1
		return dist[dst]


from typing import List
from collections import deque, defaultdict

class Solution:

	def minimumEdgeReversal(self, edges: List[List[int]], n: int, m: int, src: int, dst: int) -> int:
		queue = deque()
		graph = defaultdict(list)
		for edge in edges:
			graph[edge[0]] += [(0, edge[1])]
			graph[edge[1]] += [(1, edge[0])]
		queue.append((0, src))
		visited = set()
		while queue:
			(dist, node) = queue.popleft()
			if node == dst:
				return dist
			if node in visited:
				continue
			visited.add(node)
			for neighbor in graph[node]:
				if neighbor[1] not in visited:
					if neighbor[0] == 1:
						queue.append((dist + 1, neighbor[1]))
					else:
						queue.appendleft((dist, neighbor[1]))
		return -1


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

class Solution:

	def minimumEdgeReversal(self, edges: List[List[int]], n: int, m: int, src: int, dst: int) -> int:
		d = defaultdict(list)
		for (i, j) in edges:
			d[i].append([j, 0])
			d[j].append([i, 1])
		s = set()
		s.add((0, src))
		dist = [1000000000.0] * (n + 1)
		dist[src] = 0
		while s:
			(wt, u) = s.pop()
			for (nbr, nbrWt) in d[u]:
				if wt + nbrWt < dist[nbr]:
					s.discard((dist[nbr], nbr))
					s.add((wt + nbrWt, nbr))
					dist[nbr] = wt + nbrWt
		if dist[dst] != 1000000000.0:
			return dist[dst]
		return -1


from typing import List
import heapq

class Solution:

	def minimumEdgeReversal(self, edges: List[List[int]], n: int, m: int, src: int, dst: int) -> int:
		adj = [[] for i in range(n + 1)]
		for (u, v) in edges:
			adj[u].append([v, 0])
			adj[v].append([u, 1])
		pq = [[0, src]]
		dist = [1000000000.0] * (n + 1)
		dist[src] = 0
		while pq:
			(wt, u) = heapq.heappop(pq)
			if u == dst:
				return wt
			for (v, w) in adj[u]:
				if dist[u] != 1000000000.0 and dist[v] > dist[u] + w:
					dist[v] = dist[u] + w
					heapq.heappush(pq, [dist[v], v])
		return -1


from typing import List
from typing import List
import heapq

class Solution:

	def minimumEdgeReversal(self, edges: List[List[int]], N: int, m: int, src: int, dst: int) -> int:
		adj = [[] for i in range(n + 1)]
		for (s, t) in edges:
			adj[s].append((0, t))
			adj[t].append((1, s))
		INT_MAX = 10000000000.0
		visited = [0 for i in range(n + 1)]
		INT_MAX = 10000000000.0
		dist = [INT_MAX for i in range(n + 1)]
		dist[src] = 0
		q = [(0, src)]
		while q:
			(w, node) = heapq.heappop(q)
			for (nw, nd) in adj[node]:
				if visited[nd] == 0 and dist[nd] > dist[node] + nw:
					dist[nd] = dist[node] + nw
					heapq.heappush(q, (dist[node] + nw, nd))
			visited[node] = 1
		if dist[dst] == INT_MAX:
			return -1
		return dist[dst]


from typing import List
from collections import deque
INF = 1 << 63 - 1

class Solution:

	def minimumEdgeReversal(self, edges: List[List[int]], n: int, m: int, src: int, dst: int) -> int:
		adj = {i: [] for i in range(n + 1)}
		for (u, v) in edges:
			adj[u].append([v, 0])
			adj[v].append([u, 1])
		q = deque()
		q.append([src, 0])
		visited = [False] * (n + 1)
		while q:
			(u, step) = q.popleft()
			if u == dst:
				return step
			if visited[u]:
				continue
			visited[u] = True
			for (v, w) in adj[u]:
				if w == 0:
					q.appendleft([v, step])
				else:
					q.append([v, step + 1])
		return -1