Captain America is hiding from Thanos in a maze full of N rooms connected by M gates.
The maze is designed in such a way that each room leads to another room via gates. All connecting gates are unidirectional. Captain America is hiding only in those rooms which are accessible directly/indirectly through every other room in the maze.
Help Thanos find the number of rooms in which Captain America can hide. 
 
Example 1:
Input:
N = 5 and M = 5
V = [[1, 2], [2, 3], [3, 4], [4, 3], [5, 4]]
Output: 2
Explanation:
We can look closesly after forming graph 
than captain america only can hide in a 
room 3 and 4 because they are the only room 
which have gates through them. So,
answer is 2.
Example 2:
Input:
N = 2, M = 1
V = [[1, 2]]
Output: 1
Your Task:  
You don't need to read input or print anything. Your task is to complete the function captainAmerica() which takes the integer N, an integer M and 2-d array V as input parameters and returns the Total no of rooms.
Expected Time Complexity: O(N+M)
Expected Auxiliary Space: O(N+M)
 
Constraints:
1 ≤ n ≤ 30000
1 ≤ m ≤ 200000
1 ≤ p,q ≤ n

Source: geeksforgeeks | Difficulty: MEDIUM_HARD
Tags: Graph algorithms

Data structures

Graph traversal

Starter code: #User function Template for python3





class Solution:

    def captainAmerica (self, N, M, V):

        # code here





Solutions:
from collections import Counter, deque

class UF:

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

	def find(self, k):
		ok = k
		while self.parent[k] != k:
			k = self.parent[k]
		while self.parent[ok] != k:
			pk = self.parent[ok]
			self.parent[ok] = k
			ok = pk
		return k

	def union(self, x, y):
		px = self.find(x)
		py = self.find(y)
		self.parent[x] = py

	def getStart(self):
		cnt = Counter()
		for k in range(self.n):
			cnt[self.find(k)] += 1
		for i in range(self.n):
			if cnt[i] == self.n:
				return i
		return -1

class Solution:

	def captainAmerica(self, N, M, V):
		v = [[] for _ in range(N)]
		uf = UF(N)
		for edge in V:
			v[edge[0] - 1].append(edge[1] - 1)
			uf.union(edge[0] - 1, edge[1] - 1)
		start = uf.getStart()
		if start == -1:
			return 0
		Q = deque()
		marked = [0 for _ in range(N)]
		marked[start] = 1
		Q.append(start)
		ans = 1
		while len(Q) > 0:
			k = Q.popleft()
			for w in v[k]:
				if not marked[w]:
					ans += 1
					marked[w] = 1
					Q.append(w)
		return ans


import sys
sys.setrecursionlimit(10 ** 6)
MAX = 40000
graph = [[] for i in range(MAX)]
graphT = [[] for i in range(MAX)]
sol = []
visited = [False for i in range(MAX)]
conne = [0 for i in range(MAX)]
ini = [0 for i in range(MAX)]

class Solution:

	def dfs(self, S):
		visited[S] = True
		for v in graph[S]:
			if visited[v] == False:
				self.dfs(v)
		sol.append(S)

	def dfs2(self, S, C):
		visited[S] = False
		conne[S] = C
		for v in graphT[S]:
			if visited[v]:
				self.dfs2(v, C)

	def captainAmerica(self, N, M, V):
		sol.clear()
		for i in range(1, N + 1):
			graph[i].clear()
			graphT[i].clear()
			visited[i] = False
			conne[i] = 0
			ini[i] = 0
		for i in range(M):
			u = V[i][0]
			v = V[i][1]
			graph[v].append(u)
			graphT[u].append(v)
		for i in range(1, N + 1):
			if visited[i] == False:
				self.dfs(i)
		compon = 0
		for i in range(len(sol) - 1, 0, -1):
			if visited[sol[i]]:
				compon = compon + 1
				self.dfs2(sol[i], compon)
		lim = compon
		for i in range(1, N + 1):
			for j in range(len(graph[i])):
				if conne[i] != conne[graph[i][j]]:
					ini[conne[graph[i][j]]] = ini[conne[graph[i][j]]] + 1
		ou = 0
		for i in range(lim):
			if ini[i] == 0:
				ou = ou + 1
		if ou > 1:
			return 0
		ou = 0
		for i in range(1, N + 1):
			if ini[conne[i]] == 0:
				ou = ou + 1
		return ou


import sys
sys.setrecursionlimit(300000)

class Solution:

	def DFS(self, connections, i, killed):
		killed[i] = True
		road = []
		for connection in connections[i]:
			if not killed[connection]:
				road += self.DFS(connections, connection, killed)
		return road + [i]

	def captainAmerica(self, N, M, V):
		lim = 100000
		(victims, shooters) = ([[] for _ in range(lim)], [[] for _ in range(lim)])
		(v_0, killed, road) = ([], [False] * lim, [])
		for i in range(M):
			(shooter, victim) = V[i]
			v_0 += [[shooter - 1, victim - 1]]
			victims[shooter - 1].append(victim - 1)
			shooters[victim - 1].append(shooter - 1)
		for i in range(0, N):
			if not killed[i]:
				road += self.DFS(victims, i, killed)
		(killed, r_dfs, smap) = ([False] * lim, [], [[] for _ in range(len(road))])
		reversed_road = list(reversed(road))
		for j in reversed_road:
			if not killed[j]:
				r_dfs += [self.DFS(shooters, j, killed)]
				for node in r_dfs[-1]:
					smap[node] = len(r_dfs) - 1
		aux = [0] * len(r_dfs)
		for g in v_0:
			if smap[g[0]] != smap[g[1]]:
				aux[smap[g[0]]] += 1
		(res, cnt) = (0, 0)
		for (i, d) in enumerate(aux):
			if d == 0:
				res = len(r_dfs[i])
				cnt += 1
		return res if cnt == 1 else 0


import sys
sys.setrecursionlimit(30000)

class Solution:

	def DFS(self, connections, i, killed):
		killed[i] = True
		road = []
		for connection in connections[i]:
			if not killed[connection]:
				road += self.DFS(connections, connection, killed)
		return road + [i]

	def captainAmerica(self, N, M, V):
		(victims, shooters) = ([[] for _ in range(N + 1)], [[] for _ in range(N + 1)])
		(V_0, killed, road) = ([], [False] * (N + 1), [])
		for i in range(M):
			(shooter, victim) = V[i]
			V_0 += [[shooter - 1, victim - 1]]
			victims[shooter - 1].append(victim - 1)
			shooters[victim - 1].append(shooter - 1)
		for i in range(0, N):
			if not killed[i]:
				road += self.DFS(victims, i, killed)
		(killed, scc, smap) = ([False] * (N + 1), [], {})
		reversed_road = list(reversed(road))
		for j in reversed_road:
			if not killed[j]:
				scc += [self.DFS(shooters, j, killed)]
				for node in scc[-1]:
					smap[node] = len(scc) - 1
		sccd = [0] * len(scc)
		for g in V_0:
			if smap[g[0]] != smap[g[1]]:
				sccd[smap[g[0]]] += 1
		(res, cnt) = (0, 0)
		for (i, d) in enumerate(sccd):
			if d == 0:
				res = len(scc[i])
				cnt += 1
		return res if cnt == 1 else 0


import sys
sys.setrecursionlimit(30000)

class Solution:

	def DFS(self, victims, i, visited):
		visited[i] = True
		stk = []
		for v in victims[i]:
			if not visited[v]:
				stk += self.DFS(victims, v, visited)
		return stk + [i]

	def captainAmerica(self, N, M, V):
		(victims, shooters) = ([[] for _ in range(30000)], [[] for _ in range(30000)])
		(edges, visited, stk) = ([], [False] * 30000, [])
		for i in range(M):
			(u, v) = V[i]
			edges += [[u - 1, v - 1]]
			victims[u - 1].append(v - 1)
			shooters[v - 1].append(u - 1)
		for i in range(N):
			if not visited[i]:
				stk += self.DFS(victims, i, visited)
		(visited, scc, smap) = ([False] * 30000, [], {})
		for j in stk[::-1]:
			if not visited[j]:
				scc += [self.DFS(shooters, j, visited)]
				for node in scc[-1]:
					smap[node] = len(scc) - 1
		sccd = [0] * len(scc)
		for g in edges:
			if smap[g[0]] != smap[g[1]]:
				sccd[smap[g[0]]] += 1
		(res, cnt) = (0, 0)
		for (i, d) in enumerate(sccd):
			if d == 0:
				res = len(scc[i])
				cnt += 1
		return res if cnt == 1 else 0


import sys
sys.setrecursionlimit(10 ** 6)
MAX = 40000
graph = [[] for i in range(MAX)]
graphT = [[] for i in range(MAX)]
sol = []
visited = [False for i in range(MAX)]
conne = [0 for i in range(MAX)]
ini = [0 for i in range(MAX)]

class Solution:

	def dfs(self, S):
		visited[S] = True
		for v in graph[S]:
			if visited[v] == False:
				self.dfs(v)
		sol.append(S)

	def dfs2(self, S, C):
		visited[S] = False
		conne[S] = C
		for v in graphT[S]:
			if visited[v]:
				self.dfs2(v, C)

	def captainAmerica(self, N, M, V):
		sol.clear()
		for i in range(1, N + 1):
			graph[i].clear()
			graphT[i].clear()
			visited[i] = False
			conne[i] = 0
			ini[i] = 0
		for i in range(M):
			u = V[i][0]
			v = V[i][1]
			graph[v].append(u)
			graphT[u].append(v)
		for i in range(1, N + 1):
			if visited[i] == False:
				self.dfs(i)
		compon = 0
		for i in range(len(sol) - 1, 0, -1):
			if visited[sol[i]]:
				compon = compon + 1
				self.dfs2(sol[i], compon)
		lim = compon
		for i in range(1, N + 1):
			for j in range(len(graph[i])):
				if conne[i] != conne[graph[i][j]]:
					ini[conne[graph[i][j]]] = ini[conne[graph[i][j]]] + 1
		ou = 0
		for i in range(lim):
			if ini[i] == 0:
				ou = ou + 1
		if ou > 1:
			return 0
		ou = 0
		for i in range(1, N + 1):
			if ini[conne[i]] == 0:
				ou = ou + 1
		return ou
if __name__ == '__main__':
	ob = Solution()
	t = int(input())
	for _ in range(t):
		(N, M) = map(int, input().split())
		V = list()
		for i in range(0, M):
			l = list(map(int, input().split()))
			V.append(l)
		ans = ob.captainAmerica(N, M, V)
		print(ans)


class Solution:

	def captainAmerica(self, N, M, V):
		graph = {}
		graph1 = {}
		for i in range(N + 1):
			graph[i] = []
			graph1[i] = []
		for i in V:
			(s, d) = i
			graph[d].append(s)
			graph1[s].append(d)
		visited = [False for i in range(N + 1)]

		def bfs(v, g):
			visited[v] = True
			q = [v]
			while q:
				curr = q.pop()
				for k in g[curr]:
					if visited[k] == False:
						q.append(k)
						visited[k] = True
		mother = 0
		for k in range(1, N + 1):
			if visited[k] == False:
				bfs(k, graph)
				mother = k
		visited = [False for i in range(N + 1)]
		bfs(mother, graph)
		for i in range(1, N + 1):
			if visited[i] == False:
				return 0
		if mother == 0:
			return 0
		output = [mother]
		visited = [False for i in range(N + 1)]
		bfs(mother, graph1)
		for i in range(1, N + 1):
			if visited[i] == True and i != mother:
				output.append(i)
		s = set(output)
		return len(s)
if __name__ == '__main__':
	ob = Solution()
	t = int(input())
	for _ in range(t):
		(N, M) = map(int, input().split())
		V = list()
		for i in range(0, M):
			l = list(map(int, input().split()))
			V.append(l)
		ans = ob.captainAmerica(N, M, V)
		print(ans)


import sys
sys.setrecursionlimit(10 ** 6)

class Solution:

	def dfs(self, V, adj, visited, stack, ind):
		visited[ind] = True
		for i in adj[ind]:
			if not visited[i]:
				self.dfs(V, adj, visited, stack, i)
		stack.append(ind)

	def toposort(self, V, adj):
		stack = list()
		visited = [False] * V
		for i in range(V):
			if not visited[i]:
				self.dfs(V, adj, visited, stack, i)
		return stack

	def transpose(self, V, adj):
		new_adj = [list() for i in range(V)]
		for ind in range(V):
			for i in adj[ind]:
				new_adj[i].append(ind)
		return new_adj

	def captainAmerica(self, N, M, V):
		adj = [list() for i in range(N)]
		for val in V:
			adj[val[0] - 1].append(val[1] - 1)
		topolist = self.toposort(N, adj)
		sink_node = topolist[0]
		visited = [False] * N
		sink_connected_nodes = list()
		self.dfs(N, adj, visited, [], sink_node)
		for i in range(N):
			if visited[i]:
				sink_connected_nodes.append(i)
		new_adj = self.transpose(N, adj)
		visited = [False] * N
		self.dfs(N, new_adj, visited, [], sink_node)
		for i in range(N):
			if not visited[i]:
				return 0
		return len(sink_connected_nodes)


class Solution:

	def captainAmerica(self, n, m, v):
		adj = [[] for _ in range(n + 1)]
		loops = [[] for _ in range(n + 1)]
		for i in v:
			adj[i[1]].append(i[0])
		size = [1] * (n + 1)
		v = [0] * (n + 1)
		for i in range(1, n + 1):
			if v[i] == 0:
				s = self.dfs(i, loops, v, size, adj)
				c = self.dfs_connect(i, loops)
				if s == n:
					return len(c)
				for j in c:
					size[j] = s
		return 0

	def dfs(self, root, loops, v, size, adj):
		c = 1
		p = [root]
		while p:
			curr = p[-1]
			v[curr] = root
			while adj[curr]:
				i = adj[curr].pop()
				if v[i] == root:
					loops[i].append(curr)
				elif v[i] > 0:
					c += size[i]
				else:
					c += 1
					p.append(i)
					break
			if p[-1] == curr:
				p.pop()
		return c

	def dfs_connect(self, root, loops):
		c = {root}
		stack = [root]
		while stack:
			curr = stack.pop()
			c.update(loops[curr])
			stack.extend(loops[curr])
			loops[curr] = []
		return c


import collections

class Solution:

	def captainAmerica(self, n, m, v):

		def dfs(root, loop_edges, vis, size, adj):
			cnt = 1
			path = [root]
			while path:
				curr = path[-1]
				vis[curr] = root
				while adj[curr]:
					i = adj[curr].pop()
					if vis[i] == root:
						loop_edges[i].append(curr)
					elif vis[i] > 0:
						cnt += size[i]
					else:
						cnt += 1
						path.append(i)
						break
				if path[-1] == curr:
					path.pop()
			return cnt

		def dfs_con(root, loop_edges):
			con = {root}
			stack = [root]
			while stack:
				curr = stack.pop()
				con.update(loop_edges[curr])
				stack.extend(loop_edges[curr])
				loop_edges[curr] = []
			return con
		adj = [[] for _ in range(n + 1)]
		loop_edges = [[] for _ in range(n + 1)]
		for (i, j) in v:
			adj[j].append(i)
		size = [1] * (n + 1)
		vis = [0] * (n + 1)
		for i in range(1, n + 1):
			if not vis[i]:
				s = dfs(i, loop_edges, vis, size, adj)
				con = dfs_con(i, loop_edges)
				if s == n:
					return len(con)
				for j in con:
					size[j] = s
		return 0


class Solution:

	def captainAmerica(self, N, M, V):
		adj = [[] for i in range(N + 1)]
		loop_edges = [[] for i in range(N + 1)]
		for edge in V:
			adj[edge[1]].append(edge[0])
		size = [1] * (N + 1)
		visited = [0] * (N + 1)
		for i in range(1, N + 1):
			if visited[i] == 0:
				s = self.dfs(i, loop_edges, visited, size, adj)
				connected = self.dfs_connected(i, loop_edges)
				if s == N:
					return len(connected)
				for j in connected:
					size[j] = s
		return 0

	def dfs(self, root, loop_edges, visited, size, adj):
		count = 1
		path = [root]
		while path:
			curr = path[-1]
			visited[curr] = root
			while adj[curr]:
				i = adj[curr].pop()
				if visited[i] == root:
					loop_edges[i].append(curr)
				elif visited[i] > 0:
					count += size[i]
				else:
					count += 1
					path.append(i)
					break
			if path[-1] == curr:
				path.pop()
		return count

	def dfs_connected(self, root, loop_edges):
		connected = {root}
		stack = [root]
		while stack:
			curr = stack.pop()
			connected.update(loop_edges[curr])
			stack.extend(loop_edges[curr])
			loop_edges[curr] = []
		return connected


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

class Solution:

	def dfs(self, v, adj, vis):
		vis[v] = True
		for nbr in adj[v]:
			if not vis[nbr]:
				self.dfs(nbr, adj, vis)

	def captainAmerica(self, n, m, vlist):
		adj = collections.defaultdict(list)
		vis = [False] * (n + 1)
		for (u, v) in vlist:
			adj[v].append(u)
		parent = -1
		for i in range(1, n + 1):
			if not vis[i]:
				parent = i
				self.dfs(i, adj, vis)
		vis = [False] * (n + 1)
		self.dfs(parent, adj, vis)
		for i in range(1, n + 1):
			if not vis[i]:
				return 0
		adj = collections.defaultdict(list)
		for (u, v) in vlist:
			adj[u].append(v)
		vis = [False] * (n + 1)
		vis[parent] = True
		queue = collections.deque([parent])
		ans = 0
		while queue:
			v = queue.popleft()
			ans += 1
			for nbr in adj[v]:
				if not vis[nbr]:
					queue.append(nbr)
					vis[nbr] = True
		return ans


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

class Solution:

	def dfs(self, visited, adj, u, st):
		visited[u] = True
		st.add(u)
		for v in adj[u]:
			if not visited[v]:
				self.dfs(visited, adj, v, st)
		visited[u] = False

	def captainAmerica(self, N, M, V):
		(set1, set2) = (set(), set())
		visited = [False for i in range(N + 1)]
		adj = defaultdict(list)
		for i in range(M):
			adj[V[i][0]].append(V[i][1])
		self.dfs(visited, adj, 1, set1)
		self.dfs(visited, adj, N, set2)
		return len(set1.intersection(set2))


from sys import setrecursionlimit
setrecursionlimit(10000000)

def mgc(cur, vis, adj):
	vis.add(cur)
	for i in adj[cur]:
		if i not in vis:
			mgc(i, vis, adj)

class Solution:

	def captainAmerica(self, N, M, V):
		adj = {}
		trans = {}
		for i in range(N):
			adj[i + 1] = []
			trans[i + 1] = []
		for i in V:
			adj[i[1]].append(i[0])
			trans[i[0]].append(i[1])
		vis = set()
		last = None
		for i in range(1, N + 1):
			if i not in vis:
				mgc(i, vis, adj)
				last = i
		vis = set()
		mgc(last, vis, adj)
		if len(vis) != N:
			return 0
		vis = set()
		mgc(last, vis, trans)
		return len(vis)


from sys import setrecursionlimit
setrecursionlimit(10000000)

def mgc(cur, vis, adj):
	vis.add(cur)
	for i in adj[cur]:
		if i not in vis:
			mgc(i, vis, adj)

class Solution:

	def captainAmerica(self, N, M, V):
		adj = {}
		trans = {}
		for i in range(N):
			adj[i + 1] = []
			trans[i + 1] = []
		for i in V:
			adj[i[1]].append(i[0])
			trans[i[0]].append(i[1])
		vis = set()
		last = None
		for i in range(1, N + 1):
			if i not in vis:
				mgc(i, vis, adj)
				last = i
		vis = set()
		mgc(last, vis, adj)
		if len(vis) != N:
			return 0
		from collections import deque
		Q = deque()
		Q.append(last)
		vis = set()
		ans = 0
		vis.add(last)
		while Q:
			temp = Q.popleft()
			ans += 1
			for i in trans[temp]:
				if i not in vis:
					Q.append(i)
					vis.add(i)
		return ans


class Solution:

	def captainAmerica(self, N, M, V):
		adj = [[] for _ in range(N + 1)]
		for edge in V:
			adj[edge[1]].append(edge[0])
		size = [1] * (N + 1)
		visited = [0] * (N + 1)
		for i in range(1, N + 1):
			if not visited[i]:
				connected = {i}
				s = self.dfs([i], connected, visited, size, adj)
				if s == N:
					return len(connected)
				for j in connected:
					size[j] = s
		return 0

	def dfs(self, path, connected, visited, size, adj):
		count = 1
		while path:
			curr = path[-1]
			visited[curr] = path[0]
			adj[curr].sort(reverse=True)
			while adj[curr]:
				i = adj[curr].pop()
				if visited[i] == path[0]:
					if i in connected:
						connected.update(path)
				elif visited[i] > 0:
					count += size[i]
				else:
					count += 1
					path.append(i)
					break
			if path[-1] == curr:
				path.pop()
		return count


import sys
sys.setrecursionlimit(10 ** 6)

class Solution:

	def dfs(self, graph, u, visited, S):
		visited[u] = True
		for v in graph[u]:
			if not visited[v]:
				self.dfs(graph, v, visited, S)
		S.append(u)

	def get_topological_sort(self, graph, N):
		S = []
		visited = [False] * N
		for u in range(N):
			if not visited[u]:
				self.dfs(graph, u, visited, S)
		return S

	def get_scc(self, graph, trans, N):
		topological_sort = self.get_topological_sort(graph, N)
		scc = []
		visited = [False] * N
		while topological_sort:
			u = topological_sort.pop()
			if not visited[u]:
				component = []
				self.dfs(trans, u, visited, component)
				scc.append(component)
		return scc

	def has_outdegree(self, component, graph):
		component = set(component)
		for u in component:
			if any((v not in component for v in graph[u])):
				return True
		return False

	def captainAmerica(self, N, M, V):
		graph = [[] for _ in range(N)]
		trans = [[] for _ in range(N)]
		for (u, v) in V:
			graph[u - 1].append(v - 1)
			trans[v - 1].append(u - 1)
		scc = self.get_scc(graph, trans, N)
		(out_degree_count, max_size) = (0, 0)
		for component in scc:
			if not self.has_outdegree(component, graph):
				out_degree_count += 1
				max_size = max(max_size, len(component))
		if out_degree_count == 1:
			return max_size
		else:
			return 0


import sys
sys.setrecursionlimit(10 ** 6)

def dfs1(g, u):
	global visited1
	global stack
	visited1[u] = True
	for v in g[u]:
		if visited1[v] == False:
			dfs1(g, v)
	stack.append(u)

def transposeGraph(g):
	gT = {i: [] for i in g.keys()}
	for i in g.keys():
		for j in g[i]:
			gT[j].append(i)
	return gT

def dfs2(g, u):
	global visited2
	global count
	global scc
	scc[u] = count
	visited2[u] = True
	for v in g[u]:
		if visited2[v] == False:
			dfs2(g, v)

def stronglyConnectedComp(g):
	global visited1
	global visited2
	global count
	global stack
	global scc
	stack = []
	visited1 = {i: False for i in g.keys()}
	for i in g.keys():
		if visited1[i] == False:
			dfs1(g, i)
	gT = transposeGraph(g)
	count = 1
	scc = {i: -1 for i in g.keys()}
	visited2 = {i: False for i in g.keys()}
	while len(stack):
		k = stack.pop()
		if visited2[k] == False:
			dfs2(gT, k)
			count = count + 1
	return scc

def createGraph(n, e):
	g = {i: [] for i in range(1, n + 1)}
	for edge in e:
		u = edge[0]
		v = edge[1]
		g[u].append(v)
	return g

def buildGraphFromScc(scc, edges):
	g = {i: [] for i in scc.values()}
	for edge in edges:
		u = edge[0]
		v = edge[1]
		if scc[u] != scc[v]:
			g[scc[u]].append(scc[v])
	return g

def killCaptian(n, e):
	g = createGraph(n, e)
	scc = stronglyConnectedComp(g)
	sccGraph = buildGraphFromScc(scc, e)
	count = 0
	for i in sccGraph.values():
		if len(i) == 0:
			count = count + 1
	if count == 0 or count > 1:
		return 0
	for i in sccGraph.keys():
		if len(sccGraph[i]) == 0:
			c = 0
			for j in scc.values():
				if i == j:
					c = c + 1
			return c

class Solution:

	def captainAmerica(self, N, M, V):
		return killCaptian(N, V)