Given a Directed Graph with V vertices (Numbered from 0 to V-1) and E edges, Find the number of strongly connected components in the graph.
 
Example 1:
Input:
Output:
3
Explanation:
We can clearly see that there are 3 Strongly
Connected Components in the Graph
Example 2:
Input:
Output:
1
Explanation:
All of the nodes are connected to each other.
So, there's only one SCC.
 
Your Task:
You don't need to read input or print anything. Your task is to complete the function kosaraju() which takes the number of vertices V and edge list of the graph as inputs and returns an integer denoting the number of strongly connected components in the given graph.
 
Expected Time Complexity: O(V+E).
Expected Auxiliary Space: O(V+E).
 
Constraints:
1  ≤  V  ≤  5000
0  ≤  E  ≤  (V*(V-1))
0  ≤  u, v  ≤  V-1
Sum of E over all testcases will not exceed 25*10^{6}

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Graph algorithms

Data structures

Graph traversal

Starter code: #User function Template for python3



class Solution:

    

    #Function to find number of strongly connected components in the graph.

    def kosaraju(self, V, adj):

        # code here

Solutions:
class Solution:

	def kosaraju(self, V, adj):

		def time(G):
			n = len(G)
			visited = [False for _ in range(n)]
			time_tab = [0 for _ in range(n)]
			t = n - 1

			def dfsVisit(G, u):
				nonlocal visited, time_tab, t
				visited[u] = True
				for v in G[u]:
					if not visited[v]:
						dfsVisit(G, v)
				time_tab[t] = u
				t -= 1
			for i in range(n):
				if not visited[i]:
					dfsVisit(G, i)
			return time_tab

		def revese_edges(G):
			n = len(G)
			visited = [False for _ in range(n)]
			A = [[] for _ in range(n)]

			def dfsVisit(G, u):
				nonlocal visited
				visited[u] = True
				for v in G[u]:
					A[v].append(u)
					if not visited[v]:
						dfsVisit(G, v)
			for i in range(n):
				if not visited[i]:
					dfsVisit(G, i)
			return A

		def strong_connected_components(G):
			n = len(G)
			A = revese_edges(G)
			time_tab = time(G)
			visited = [False for _ in range(n)]
			out = []

			def dfsVisit(A, u):
				nonlocal visited, comp
				visited[u] = True
				for v in A[u]:
					if not visited[v]:
						dfsVisit(A, v)
				comp.append(u)
			for v in time_tab:
				if not visited[v]:
					comp = []
					dfsVisit(A, v)
					out += [comp]
			return out
		return len(strong_connected_components(adj))


from collections import deque

class Solution:

	def dfs(self, node, adj, visited, stk, first):
		visited[node] = True
		for adjNode in adj[node]:
			if not visited[adjNode]:
				self.dfs(adjNode, adj, visited, stk, first)
		if first:
			stk.append(node)

	def kosaraju(self, V, adj):
		(res, stk, visited) = (0, deque(), [False] * V)
		for node in range(V):
			if not visited[node]:
				self.dfs(node, adj, visited, stk, True)
		revAdj = [[] for i in range(V)]
		for a in range(V):
			for b in adj[a]:
				revAdj[b].append(a)
		visited = [False] * V
		while stk:
			node = stk.pop()
			if not visited[node]:
				res += 1
				self.dfs(node, revAdj, visited, stk, False)
		return res


class Solution:

	def reverse_graph(self, adj, adjt):
		for v in range(V):
			for neigh in adj[v]:
				adjt[neigh].append(v)
		return adjt

	def dfs(self, sv, visited, stack):
		visited[sv] = True
		for neigh in adj[sv]:
			if visited[neigh] == False:
				self.dfs(neigh, visited, stack)
		stack.append(sv)

	def dfsr(self, sv, visitedr, adjt):
		visitedr[sv] = True
		for neigh in adjt[sv]:
			if visitedr[neigh] == False:
				self.dfsr(neigh, visitedr, adjt)
		return

	def kosaraju(self, V, adj):
		visited = [False for i in range(V)]
		stack = []
		for i in range(V):
			if visited[i] == False:
				self.dfs(i, visited, stack)
		adjt = [[] for i in range(V)]
		adjt = self.reverse_graph(adj, adjt)
		c = 0
		visitedr = [False for i in range(V)]
		while len(stack) != 0:
			x = stack.pop()
			if visitedr[x] == False:
				c += 1
				self.dfsr(x, visitedr, adjt)
		return c


class Solution:

	def kosaraju(self, V, adj):
		return my_kosaraju(adj)
from collections import deque

def DFS(graph, node, visited, stack):
	visited[node] = True
	for neighbor in graph[node]:
		if not visited[neighbor]:
			DFS(graph, neighbor, visited, stack)
	stack.append(node)

def transpose(graph):
	num_nodes = len(graph)
	transposed_graph = [[] for _ in range(num_nodes)]
	for node in range(num_nodes):
		for neighbor in graph[node]:
			transposed_graph[neighbor].append(node)
	return transposed_graph

def my_kosaraju(graph):
	num_nodes = len(graph)
	visited = [False] * num_nodes
	stack = []
	for node in range(num_nodes):
		if not visited[node]:
			DFS(graph, node, visited, stack)
	transposed = transpose(graph)
	visited = [False] * num_nodes
	components = []
	while stack:
		node = stack.pop()
		if not visited[node]:
			component = []
			DFS(transposed, node, visited, component)
			components.append(component)
	return len(components)


class Solution:

	def kosaraju(self, V, adj):

		def dfs(node, v, adj):
			v.add(node)
			for nbr in adj[node]:
				if nbr not in v:
					dfs(nbr, v, adj)
			stack.append(node)

		def transpose(adj):
			adjRev = [[] for _ in range(V)]
			for i in range(V):
				for j in adj[i]:
					adjRev[j].append(i)
			return adjRev

		def dfs2(node, v, adjRev):
			v.add(node)
			for nbr in adjRev[node]:
				if nbr not in v:
					dfs(nbr, v, adjRev)
		v = set()
		stack = []
		for src in range(V):
			if src not in v:
				dfs(src, v, adj)
		adjRev = transpose(adj)
		v = set()
		scc = 0
		while stack:
			src = stack.pop()
			if src not in v:
				scc += 1
				dfs2(src, v, adjRev)
		return scc


class Solution:

	def kosaraju(self, V, adj):

		def dfs(node, visited, stack):
			visited.add(node)
			for i in adj[node]:
				if i not in visited:
					dfs(i, visited, stack)
			stack.append(node)
		visited = set()
		stack = []
		for i in range(V):
			if i not in visited:
				dfs(i, visited, stack)
		adjT = [[] for i in range(V)]
		for i in range(V):
			for node in adj[i]:
				adjT[node].append(i)

		def dfs1(i, visited1, adjT):
			visited1.add(i)
			for j in adjT[i]:
				if j not in visited1:
					dfs1(j, visited1, adjT)
		visited1 = set()
		scc = 0
		stack = stack[::-1]
		for x in stack:
			if x not in visited1:
				scc += 1
				dfs1(x, visited1, adjT)
		return scc


from collections import defaultdict

class Solution:

	def topo(self, node, adj, vis, st):
		vis[node] = 1
		for i in adj[node]:
			if vis[i] == 0:
				self.topo(i, adj, vis, st)
		st.append(node)

	def dfs(self, node, adj, vis):
		vis[node] = 1
		for i in adj[node]:
			if vis[i] == 0:
				self.dfs(i, adj, vis)

	def kosaraju(self, V, adj):
		vis = [0] * V
		st = []
		for i in range(V):
			if vis[i] == 0:
				self.topo(i, adj, vis, st)
		reverse = [[] for i in range(V)]
		for i in range(V):
			for j in adj[i]:
				reverse[j].append(i)
		vis = [0] * V
		count = 0
		while len(st) > 0:
			node = st.pop()
			if vis[node] == 0:
				count += 1
				self.dfs(node, reverse, vis)
		return count


from collections import *

class Solution:

	def kosaraju(self, V, adj):
		rev = defaultdict(list)
		for i in range(V):
			for j in adj[i]:
				rev[j].append(i)
		order = []
		visit = [False] * V

		def dfsord(src, visit, adj):
			visit[src] = True
			for i in adj[src]:
				if not visit[i]:
					dfsord(i, visit, adj)
			order.append(src)

		def normdfs(src, newvisit, rev):
			newvisit[src] = True
			for i in rev[src]:
				if not newvisit[i]:
					normdfs(i, newvisit, rev)
		for i in range(V):
			if not visit[i]:
				dfsord(i, visit, adj)
		ans = 0
		newvisit = [False] * V
		for i in range(V - 1, -1, -1):
			if not newvisit[order[i]]:
				ans += 1
				normdfs(order[i], newvisit, rev)
		return ans


class Solution:

	def kosaraju(self, V, adj):

		def dfs1(i):
			if i in v:
				return i
			else:
				v.add(i)
				for j in adj[i]:
					dfs1(j)
			stk.append(i)

		def dfs2(i):
			if i in v:
				return
			else:
				v.add(i)
				for j in adj1[i]:
					dfs2(j)
		adj1 = [[] for i in range(V)]
		for i in range(len(adj)):
			for j in adj[i]:
				adj1[j].append(i)
		stk = []
		v = set()
		for i in range(V):
			if i not in v:
				dfs1(i)
		v = set()
		c = 0
		for i in stk[::-1]:
			if i not in v:
				dfs2(i)
				c += 1
		return c


class Solution:

	def kosaraju(self, V, adj1):
		visited1 = [0] * V
		visited2 = [0] * V
		stack1 = []
		stack2 = []

		def dfs(node, stack, visited, adj):
			visited[node] = 1
			for u in adj[node]:
				if visited[u] == 0:
					dfs(u, stack, visited, adj)
			stack.append(node)
		for i in range(V):
			if visited1[i] == 0:
				dfs(i, stack1, visited1, adj1)
		adj_rev = [[] for _ in range(len(adj1))]
		for u in range(V):
			for v in adj1[u]:
				adj_rev[v].append(u)
		ans = 0
		while stack1:
			x = stack1.pop()
			if visited2[x] == 0:
				dfs(x, stack2, visited2, adj_rev)
				ans += 1
		return ans


class Solution:

	def dfs(self, vis, node, st, adj):
		vis[node] = 1
		for i in adj[node]:
			if vis[i] == 0:
				self.dfs(vis, i, st, adj)
		st.append(node)

	def dfs2(self, vis, node, adj):
		vis[node] = 1
		for i in adj[node]:
			if vis[i] == 0:
				self.dfs2(vis, i, adj)

	def kosaraju(self, V, adj):
		vis = [0] * V
		st = []
		cnt = 0
		for i in range(V):
			if vis[i] == 0:
				self.dfs(vis, i, st, adj)
		adjrev = [[] for i in range(V)]
		for i in range(V):
			l = adj[i]
			for j in l:
				adjrev[j].append(i)
		st = st[::-1]
		vis = [0] * V
		for i in st:
			if vis[i] == 0:
				self.dfs2(vis, i, adjrev)
				cnt += 1
		return cnt


from collections import deque

class Solution:

	def dfs(self, node, adj, vis, st):
		vis[node] = 1
		for adjNode in adj[node]:
			if not vis[adjNode]:
				Solution.dfs(self, adjNode, adj, vis, st)
		st.append(node)

	def dfs2(self, node, adj, vis):
		vis[node] = 1
		for adjNode in adj[node]:
			if not vis[adjNode]:
				Solution.dfs2(self, adjNode, adj, vis)

	def kosaraju(self, V, adj):
		vis = [0] * V
		st = deque()
		for i in range(V):
			if not vis[i]:
				Solution.dfs(self, i, adj, vis, st)
		adjT = [[] for i in range(V)]
		for i in range(V):
			vis[i] = 0
			for adjNode in adj[i]:
				adjT[adjNode].append(i)
		scc = 0
		while len(st) != 0:
			node = st.pop()
			if not vis[node]:
				scc += 1
				Solution.dfs2(self, node, adjT, vis)
		return scc


class Solution:

	def dfs(self, node, vis, adj, st):
		vis[node] = 1
		for it in adj[node]:
			if vis[it] == 0:
				self.dfs(it, vis, adj, st)
		st.append(node)

	def dfs3(self, node, vis, adjT):
		vis[node] = 1
		for it in adjT[node]:
			if vis[it] == 0:
				self.dfs3(it, vis, adjT)

	def kosaraju(self, V, adj):
		(vis, st) = ([0] * V, [])
		for i in range(V):
			if vis[i] == 0:
				self.dfs(i, vis, adj, st)
		adjT = [[] for _ in range(V)]
		for i in range(V):
			vis[i] = 0
			for it in adj[i]:
				adjT[it].append(i)
		scc = 0
		while st:
			node = st[-1]
			st.pop()
			if vis[node] == 0:
				scc += 1
				self.dfs3(node, vis, adjT)
		return scc


class Solution:

	def kosaraju(self, V, adj):

		def sss(G):

			def DFSVisit(G, u):
				nonlocal ix
				visited[u] = True
				for v in G[u]:
					G1[v].append(u)
					if not visited[v]:
						DFSVisit(G, v)
				time[ix] = u
				ix -= 1

			def sssVisit(G1, u, comp_no):
				visited[u] = False
				for v in G1[u]:
					if visited[v]:
						sssVisit(G1, v, comp_no)
			n = len(G)
			G1 = [[] for _ in range(n)]
			time = [0] * n
			visited = [False for _ in range(n)]
			ix = n - 1
			for u in range(n):
				if not visited[u]:
					DFSVisit(G, u)
			comp_count = 0
			for u in time:
				if visited[u]:
					sssVisit(G1, u, comp_count)
					comp_count += 1
			return comp_count
		return sss(adj)


class Solution:

	def kosaraju(self, V, adj):

		def findNodeOrder(node, count):
			if node in store:
				return count
			store[node] = 1
			for item in adj[node]:
				count = findNodeOrder(item, count)
			count += 1
			store[node] = count
			num.append(count)
			return count
		store = {}
		num = [0]
		for node in range(V):
			findNodeOrder(node, num[-1])
		nodes = [key for (key, value) in sorted(store.items(), key=lambda x: -x[1])]
		reverse_adj = [[] for _ in range(V)]
		for (i, lista) in enumerate(adj):
			for node in lista:
				reverse_adj[node].append(i)
		count = 0
		visited = set()
		for node in nodes:
			if node in visited:
				continue
			count += 1
			stack = [node]
			while stack:
				node = stack.pop()
				if node in visited:
					continue
				visited.add(node)
				stack += reverse_adj[node]
		return count


class Solution:

	def kosaraju(self, V, adj):
		s = []
		vis = [False] * (V + 1)

		def dfs(node, vis, s, adj, V):
			vis[node] = True
			for neighbour in adj[node]:
				if not vis[neighbour]:
					dfs(neighbour, vis, s, adj, V)
			s.append(node)
		for i in range(V):
			if not vis[i]:
				dfs(i, vis, s, adj, V)
		trans = [[] for i in range(V)]
		for i in range(V):
			vis[i] = False
			for j in range(len(adj[i])):
				trans[adj[i][j]].append(i)

		def revdfs(node, vis, adj, V):
			vis[node] = True
			for i in adj[node]:
				if not vis[i]:
					revdfs(i, vis, adj, V)
		count = 0
		while len(s) != 0:
			top = s.pop()
			if not vis[top]:
				count += 1
				revdfs(top, vis, trans, V)
		return count


class Solution:

	def kosaraju(self, V, adj):
		stack = []
		visited = [False] * V

		def dfs(node):
			visited[node] = True
			for neighbor in adj[node]:
				if not visited[neighbor]:
					dfs(neighbor)
			stack.append(node)
		for node in range(V):
			if not visited[node]:
				dfs(node)
		adj_reverse = [[] for _ in range(V)]
		for node in range(V):
			for neighbor in adj[node]:
				adj_reverse[neighbor].append(node)
		visited = [False] * V

		def dfs_reverse(node):
			visited[node] = True
			for neighbor in adj_reverse[node]:
				if not visited[neighbor]:
					dfs_reverse(neighbor)
		num_scc = 0
		while stack:
			node = stack.pop()
			if not visited[node]:
				dfs_reverse(node)
				num_scc += 1
		return num_scc


from collections import defaultdict

class Solution:

	def reverse_graph(self, V, adj):
		rev_adj = defaultdict(list)
		for i in range(V):
			for j in adj[i]:
				rev_adj[j].append(i)
		return rev_adj

	def kosaraju(self, V, adj):
		(stack, visited) = ([], [False] * V)

		def dfs(u):
			if visited[u]:
				return
			visited[u] = True
			for v in adj[u]:
				dfs(v)
			stack.append(u)
		for i in range(V):
			if not visited[i]:
				dfs(i)
		rev_adj = self.reverse_graph(V, adj)

		def dfs2(u):
			if visited[u]:
				return
			visited[u] = True
			for v in rev_adj[u]:
				dfs2(v)
		visited = [False for _ in range(V)]
		count = 0
		for i in range(len(stack) - 1, -1, -1):
			val = stack[i]
			if not visited[val]:
				dfs2(val)
				count += 1
		return count


class Solution:

	def dfs(self, node, adj, st, vis):
		vis[node] = 1
		for nei in adj[node]:
			if vis[nei] != 1:
				self.dfs(nei, adj, st, vis)
		st.append(node)

	def revdfs(self, node, adjT, vis):
		vis[node] = 1
		for nei in adjT[node]:
			if vis[nei] != 1:
				self.revdfs(nei, adjT, vis)

	def kosaraju(self, V, adj):
		vis = [0 for _ in range(V)]
		st = list()
		for i in range(V):
			if vis[i] != 1:
				self.dfs(i, adj, st, vis)
		adjT = [[] for _ in range(V)]
		for i in range(V):
			vis[i] = 0
			for nei in adj[i]:
				adjT[nei].append(i)
		res = 0
		while st:
			node = st.pop()
			if vis[node] != 1:
				self.revdfs(node, adjT, vis)
				res += 1
		return res


from collections import defaultdict

class Solution:

	def kosaraju(self, V, adj):
		visited1 = [0] * V
		st = []

		def dfs(node):
			visited1[node] = 1
			for nei in adj[node]:
				if not visited1[nei]:
					dfs(nei)
			st.append(node)
		for node in range(V):
			if not visited1[node]:
				dfs(node)
		graph = {i: [] for i in range(V)}
		for node in range(V):
			for nei in adj[node]:
				graph[nei].append(node)
		visited2 = [0] * V

		def dfs2(node):
			visited2[node] = 1
			for nei in graph[node]:
				if not visited2[nei]:
					dfs2(nei)
		count = 0
		while st:
			node = st.pop()
			if not visited2[node]:
				count += 1
				dfs2(node)
		return count


class Solution:

	def dfs(self, i, adj, vis, st):
		vis[i] = 1
		for it in adj[i]:
			if vis[it] == 0:
				self.dfs(it, adj, vis, st)
		st.append(i)

	def dfs2(self, i, adj, vis):
		vis[i] = 1
		for it in adj[i]:
			if vis[it] == 0:
				self.dfs2(it, adj, vis)

	def kosaraju(self, V, adj):
		vis = [0] * V
		st = []
		for i in range(V):
			if vis[i] == 0:
				self.dfs(i, adj, vis, st)
		adjt = [[] for i in range(V)]
		for i in range(V):
			vis[i] = 0
			for it in adj[i]:
				adjt[it].append(i)
		scc = 0
		while st:
			node = st.pop()
			if vis[node] == 0:
				scc += 1
				self.dfs2(node, adjt, vis)
		return scc


def count_strongly_connected_components(v, adj: [[]]):
	rev_graph = get_rev_adj(v, adj)
	order_stack = []
	visited = [False] * v
	for i in range(v):
		if not visited[i]:
			dfs_util(i, visited, adj, order_stack)
	count = 0
	visited = [False] * v
	for i in reversed(range(v)):
		vertex = order_stack[i]
		if not visited[vertex]:
			count = count + 1
			dfs_util(vertex, visited, rev_graph, [])
	return count

def dfs_util(vertex: int, visited: [], graph_adj: [[]], order_stack: []):
	if visited[vertex]:
		return
	visited[vertex] = True
	for neighbor in graph_adj[vertex]:
		dfs_util(neighbor, visited, graph_adj, order_stack)
	order_stack.append(vertex)

def get_rev_adj(v, adj: [[]]):
	rev_adj = [[] for i in range(v)]
	for i in range(len(adj)):
		vertex = i
		neighbours = adj[i]
		for neighbour in neighbours:
			rev_adj[neighbour].append(vertex)
	return rev_adj

class Solution:

	def kosaraju(self, V, adj):
		return count_strongly_connected_components(V, adj)


from collections import defaultdict

class Solution:

	def revDfs(self, node, vis, transpose):
		vis.add(node)
		for neighbr in transpose[node]:
			if neighbr not in vis:
				self.revDfs(neighbr, vis, transpose)

	def dfs(self, node, vis, stk, adj):
		vis.add(node)
		for neighbr in adj[node]:
			if neighbr not in vis:
				self.dfs(neighbr, vis, stk, adj)
		stk.append(node)

	def kosaraju(self, V, adj):
		stk = []
		vis = set()
		transpose = defaultdict(list)
		for i in range(V):
			if i not in vis:
				self.dfs(i, vis, stk, adj)
		vis.clear()
		for i in range(V):
			for nbr in adj[i]:
				transpose[nbr].append(i)
		ans = 0
		while stk:
			top = stk.pop()
			if top not in vis:
				ans += 1
				self.revDfs(top, vis, transpose)
		return ans


class Solution:

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

		def dfs(node, adjm):
			visited[node] = 1
			for each in adjm[node]:
				if not visited[each]:
					dfs(each, adjm)
			stack.append(node)
		for i in range(V):
			if not visited[i]:
				dfs(i, adj)
		adjl = [[] for _ in range(V)]
		for i in range(V):
			for j in adj[i]:
				adjl[j].append(i)
		visited = [0] * V
		stack2 = stack.copy()
		cnt = 0
		while stack2:
			if not visited[stack2[-1]]:
				cnt += 1
				dfs(stack2.pop(), adjl)
			else:
				stack2.pop()
		return cnt


from collections import deque

class Solution:

	def kosaraju(self, V, adj):
		topo = []
		vis = set()

		def order(node):
			vis.add(node)
			for child in adj[node]:
				if child not in vis:
					order(child)
			topo.append(node)
		for i in range(V):
			if i not in vis:
				order(i)
		revadj = [[] for i in range(V)]
		for node in range(V):
			for child in adj[node]:
				revadj[child].append(node)
		vis = set()

		def dfs(node):
			vis.add(node)
			for child in revadj[node]:
				if child not in vis:
					dfs(child)
		ans = 0
		for node in reversed(topo):
			if node not in vis:
				dfs(node)
				ans += 1
		return ans


from collections import defaultdict

class Solution:

	def dfs(self, i, adj, vis, st):
		vis[i] = 1
		for it in adj[i]:
			if not vis[it]:
				self.dfs(it, adj, vis, st)
		st.append(i)

	def dfs2(self, i, vis, adjT):
		vis[i] = 1
		for it in adjT[i]:
			if not vis[it]:
				self.dfs2(it, vis, adjT)

	def kosaraju(self, V, adj):
		vis = [0] * V
		st = []
		for i in range(V):
			if not vis[i]:
				self.dfs(i, adj, vis, st)
		adjT = defaultdict(list)
		for i in range(V):
			for it in adj[i]:
				adjT[it].append(i)
		vis = [0] * V
		scc = 0
		while st:
			node = st.pop()
			if vis[node] == 0:
				scc += 1
				self.dfs2(node, vis, adjT)
		return scc


from collections import deque

class Solution:

	def kosaraju(self, V, adj):
		stack = deque()
		vis = [0] * V
		onstack = [0] * V
		low = [float('inf')] * V
		tin = [0] * V
		cnt = [0]

		def rec(node, parent):
			vis[node] = 1
			(tin[node], low[node]) = (cnt[0], cnt[0])
			cnt[0] += 1
			for child in adj[node]:
				if vis[child] == 0:
					stack.append(child)
					onstack[child] = 1
					rec(child, node)
					low[node] = min(low[node], low[child])
				elif onstack[child] == 1:
					low[node] = min(low[node], tin[child])
			if low[node] == tin[node]:
				temp = stack.pop()
				onstack[temp] = 0
				while temp != node:
					low[temp] = low[node]
					temp = stack.pop()
					onstack[temp] = 0
		for i in range(V):
			if vis[i] == 0:
				onstack[i] = 1
				stack.append(i)
				rec(i, -1)
		return len(set(low))


from collections import *

class Solution:

	def dfs(self, node, vis, adj):
		vis[node] = 1
		for child in adj[node]:
			if vis[child] == 0:
				self.dfs(child, vis, adj)

	def topo(self, node, vis, adj, st):
		vis[node] = 1
		for child in adj[node]:
			if vis[child] == 0:
				self.topo(child, vis, adj, st)
		st.append(node)

	def kosaraju(self, V, adj):
		vis = [0] * V
		st = []
		for i in range(V):
			if vis[i] == 0:
				self.topo(i, vis, adj, st)
		rev_adj = defaultdict(list)
		for i in range(V):
			for j in adj[i]:
				rev_adj[j].append(i)
		vis = [0] * V
		cnt = 0
		while len(st) > 0:
			node = st.pop()
			if vis[node] == 0:
				cnt += 1
				self.dfs(node, vis, rev_adj)
		return cnt


from collections import defaultdict

class Solution:

	def dfs(self, node, visited, adjList, stack):
		visited[node] = 1
		for neighbour in adjList[node]:
			if not visited[neighbour]:
				self.dfs(neighbour, visited, adjList, stack)
		stack.append(node)

	def dfs2(self, node, visited, adjListT):
		visited[node] = 1
		for neighbour in adjListT[node]:
			if not visited[neighbour]:
				self.dfs2(neighbour, visited, adjListT)

	def kosaraju(self, V, adj):
		visited = [0] * V
		stack = []
		for i in range(V):
			if not visited[i]:
				self.dfs(i, visited, adj, stack)
		adjT = defaultdict(list)
		for i in range(V):
			visited[i] = 0
			for j in adj[i]:
				adjT[j].append(i)
		sccCount = 0
		while stack:
			node = stack.pop()
			if not visited[node]:
				sccCount += 1
				self.dfs2(node, visited, adjT)
		return sccCount


class Solution:

	def kosaraju(self, V, adj):
		visited = set()
		stk = []
		scc = 0
		reversedAdj = [[] for i in range(V)]

		def dfs1(node):
			visited.add(node)
			for neib in adj[node]:
				if neib not in visited:
					dfs1(neib)
			stk.append(node)

		def dfs2(node):
			visited.add(node)
			for neib in reversedAdj[node]:
				if neib not in visited:
					dfs2(neib)
		for node in range(V):
			if node not in visited:
				dfs1(node)
		for node in range(V):
			for neib in adj[node]:
				reversedAdj[neib].append(node)
		visited = set()
		while stk:
			node = stk.pop(-1)
			if node not in visited:
				scc += 1
				dfs2(node)
		return scc


class Solution:

	def kosaraju(self, V, adj):
		count = 1
		vis = [False] * V
		st = []
		for i in range(V):
			if vis[i] == False:
				self.DFS(i, adj, vis, st)
		adj_new = [[] for i in range(V)]
		for i in range(V):
			for j in adj[i]:
				adj_new[j].append(i)
		vis = [False] * V
		fncount = 0
		while st:
			i = st.pop()
			if vis[i] == False:
				fncount += 1
				self.fcaller(i, adj_new, vis)
		return fncount

	def fcaller(self, s, adj_new, vis):
		vis[s] = True
		for j in adj_new[s]:
			if vis[j] == False:
				self.fcaller(j, adj_new, vis)

	def DFS(self, s, adj, vis, st):
		vis[s] = True
		for j in adj[s]:
			if vis[j] == False:
				self.DFS(j, adj, vis, st)
		st.append(s)


from collections import defaultdict

class Solution:

	def kosaraju(self, V, adj):
		st = []

		def dfs1(node):
			visited[node] = 1
			for nei in adj[node]:
				if not visited[nei]:
					dfs1(nei)
			st.append(node)
		visited = [0] * V
		for node in range(V):
			if not visited[node]:
				dfs1(node)
		rev = [[] for _ in range(V)]
		for node in range(V):
			for nei in adj[node]:
				rev[nei].append(node)
		count = 0
		visited2 = [0] * V

		def dfs2(node):
			visited2[node] = 1
			for nei in rev[node]:
				if not visited2[nei]:
					dfs2(nei)
		while st:
			node = st.pop()
			if not visited2[node]:
				count += 1
				dfs2(node)
		return count


from collections import defaultdict

class Solution:

	def kosaraju(self, V, adj):
		visited = [0] * V
		arr = []
		for i in range(V):
			if not visited[i]:
				self.dfs(visited, adj, arr, i)
		adjT = defaultdict(list)
		for i in range(V):
			for u in adj[i]:
				adjT[u].append(i)
		visited = [0] * V
		cnt = 0
		while arr:
			i = arr.pop()
			if not visited[i]:
				cnt += 1
				self.dfs2(visited, adjT, i)
		return cnt

	def dfs2(self, visited, adj, s):
		visited[s] = 1
		for u in adj[s]:
			if not visited[u]:
				self.dfs2(visited, adj, u)

	def dfs(self, visited, adj, arr, s):
		visited[s] = 1
		for u in adj[s]:
			if not visited[u]:
				self.dfs(visited, adj, arr, u)
		arr.append(s)


from collections import deque

class Solution:

	def kosaraju(self, V, adj):

		def dfs(sv):
			visit[sv] = 1
			for i in adj[sv]:
				if visit[i] == 0:
					dfs(i)
			topo.append(sv)

		def revDfs(sv):
			visited[sv] = 1
			for i in new_adj[sv]:
				if visited[i] == 0:
					revDfs(i)
		visit = [0] * V
		topo = []
		for i in range(V):
			if visit[i] == 0:
				dfs(i)
		new_adj = [[] for i in range(V)]
		for i in range(V):
			for j in adj[i]:
				new_adj[j].append(i)
		c = 0
		visited = [0] * V
		for i in topo[::-1]:
			if visited[i] == 0:
				c += 1
				revDfs(i)
		return c


class Solution:

	def kosaraju(self, V, graph):

		def dfs1(v):
			visited.add(v)
			for u in graph[v]:
				if u not in visited:
					dfs1(u)
			stack.append(v)

		def dfs2(v):
			visited.add(v)
			component.add(v)
			for u in graph_r[v]:
				if u not in visited:
					dfs2(u)
		n = len(graph)
		graph_r = [[] for _ in range(n)]
		for u in range(n):
			for v in graph[u]:
				graph_r[v].append(u)
		visited = set()
		stack = []
		for v in range(n):
			if v not in visited:
				dfs1(v)
		visited = set()
		components = []
		while stack:
			v = stack.pop()
			if v not in visited:
				component = set()
				dfs2(v)
				components.append(component)
		return len(components)


class Solution:

	def kosaraju(self, V, adj):
		visited = [False] * V
		stack = []

		def dfs(node):
			visited[node] = True
			for i in adj[node]:
				if not visited[i]:
					dfs(i)
			stack.append(node)

		def dfs2(node):
			visited[node] = True
			for i in adjT[node]:
				if not visited[i]:
					dfs2(i)
		for i in range(V):
			if not visited[i]:
				dfs(i)
		adjT = [[] for _ in range(V)]
		for i in range(V):
			visited[i] = False
			for j in adj[i]:
				adjT[j].append(i)
		count = 0
		while stack:
			node = stack.pop()
			if not visited[node]:
				dfs2(node)
				count += 1
		return count


class Solution:

	def kosaraju(self, n, connections):

		def dfs(node, visited, stack):
			visited.add(node)
			for nei in connections[node]:
				if nei not in visited:
					dfs(nei, visited, stack)
			stack.append(node)
		visited = set()
		stack = []
		for i in range(n):
			if i not in visited:
				dfs(i, visited, stack)

		def reverseGraph(adj):
			new_adj = [[] for _ in range(n)]
			for i in range(n):
				for v in adj[i]:
					new_adj[v].append(i)
			return new_adj
		connections = reverseGraph(connections)
		visited.clear()
		self.result = 0
		while len(stack) != 0:
			node = stack.pop()
			if node not in visited:
				dfs(node, visited, [])
				self.result += 1
		return self.result


class Solution:

	def dfs_rec(self, visited, stack, curr, adj):
		for neighb in adj[curr]:
			if visited[neighb] == 0:
				visited[neighb] = 1
				self.dfs_rec(visited, stack, neighb, adj)
		stack.append(curr)
		return

	def transpose(self, adj, V):
		new = []
		for i in range(V):
			new.append([])
		for i in range(V):
			for j in adj[i]:
				new[j].append(i)
		return new

	def kosaraju(self, V, adj):
		stack = []
		visited = [0] * V
		for i in range(V):
			if visited[i] == 0:
				visited[i] = 1
				self.dfs_rec(visited, stack, i, adj)
		trans_adj = self.transpose(adj, V)
		visited = [0] * V
		stack2 = []
		scc = 0
		for i in range(V):
			curr = stack.pop()
			if visited[curr] == 0:
				scc = scc + 1
				stack2.append(curr)
				visited[curr] = 1
				while len(stack2) > 0:
					curr2 = stack2.pop()
					for neighb in trans_adj[curr2]:
						if visited[neighb] == 0:
							visited[neighb] = 1
							stack2.append(neighb)
		return scc


class Solution:

	def kosaraju(self, V, adj):
		ref = []
		check = [[] for i in range(V)]
		vis = set()
		for i in range(V):
			for j in adj[i]:
				check[j].append(i)

		def topologicalsort(sv):
			vis.add(sv)
			for des in adj[sv]:
				if des not in vis:
					topologicalsort(des)
			ref.append(sv)

		def dfs(sv):
			visited.add(sv)
			for des in check[sv]:
				if des not in visited:
					dfs(des)
		for i in range(V):
			if i not in vis:
				topologicalsort(i)
		visited = set()
		count = 0
		for i in range(V):
			temp = ref.pop()
			if temp not in visited:
				dfs(temp)
				count += 1
		return count


class Solution:

	def dfs(self, node, adj, vis, stack):
		vis[node] = 1
		for i in adj[node]:
			if vis[i] == 0:
				self.dfs(i, adj, vis, stack)
		stack.append(node)

	def revdfs(self, node, transpose, vis):
		vis[node] = 1
		for i in transpose[node]:
			if vis[i] == 0:
				self.revdfs(i, transpose, vis)

	def kosaraju(self, V, adj):
		stack = []
		vis = [0 for i in range(V)]
		for i in range(V):
			if vis[i] == 0:
				self.dfs(i, adj, vis, stack)
		transpose = [[] for i in range(V)]
		for i in range(V):
			vis[i] = 0
			for it in adj[i]:
				transpose[it].append(i)
		scc = 0
		while stack:
			i = stack.pop()
			if vis[i] == 0:
				self.revdfs(i, transpose, vis)
				scc += 1
		return scc


class Solution:

	def kosaraju(self, V, adj):
		vis = [0 for u in range(V)]
		__st = []
		for i in range(V):
			if vis[i] == 0:
				node = i
				self.dfs(node, vis, adj, __st)
		adjR = [[] for i in range(V)]
		for i in range(V):
			vis[i] = 0
			for n in adj[i]:
				adjR[n].append(i)
		scc = 0
		while __st:
			node = __st.pop()
			if vis[node] == 0:
				scc += 1
				self.dfs3(node, vis, adjR)
		return scc

	def dfs(self, node, vis, adj, st: list):
		vis[node] = 1
		for n in adj[node]:
			if vis[n] == 0:
				self.dfs(n, vis, adj, st)
		st.append(node)

	def dfs3(self, node, vis, adj):
		vis[node] = 1
		for n in adj[node]:
			if vis[n] == 0:
				self.dfs3(n, vis, adj)


class Solution:

	def kosaraju(self, V, adj):
		edges = []
		for i in range(len(adj)):
			for j in adj[i]:
				edges.append([i, j])
		adj_list = [[] for i in range(V)]
		for (x, y) in edges:
			adj_list[x].append(y)

		def dfs(a, adj_list, vst, toposort):
			vst[a] = 1
			for node in adj_list[a]:
				if not vst[node]:
					dfs(node, adj_list, vst, toposort)
			toposort.append(a)
		toposort = []
		vst = [0 for i in range(V)]
		for i in range(V):
			if not vst[i]:
				dfs(i, adj_list, vst, toposort)
		toposort = toposort[::-1]
		new_list = [[] for i in range(V)]
		for (x, y) in edges:
			new_list[y].append(x)
		vst = [0 for i in range(V)]
		ans = 0
		for i in toposort:
			if not vst[i]:
				temp = []
				dfs(i, new_list, vst, temp)
				ans += 1
		return ans


class Solution:

	def kosaraju(self, V, adj):
		answer = 0
		visited = [False for _ in range(V)]
		for i in range(V):
			if not visited[i]:
				answer += self.helper1(V, adj, visited, i)
		return answer

	def helper1(self, V, adj, visited, index):
		stack = []
		self.helper2(V, adj, stack, visited, index)
		revGraph = self.helper3(V, adj)
		return self.helper4(V, revGraph, stack)

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

	def helper3(self, V, adj):
		revGraph = [[] for _ in range(V)]
		for i in range(V):
			for j in adj[i]:
				revGraph[j].append(i)
		return revGraph

	def helper4(self, V, revGraph, stack):
		visited = [False for _ in range(V)]
		answer = 0
		while stack:
			element = stack.pop()
			if visited[element]:
				continue
			answer += 1
			self.helper5(V, revGraph, visited, element)
		return answer

	def helper5(self, V, revGraph, visited, element):
		visited[element] = True
		for adj in revGraph[element]:
			if not visited[adj]:
				self.helper5(V, revGraph, visited, adj)


from collections import defaultdict

class Solution:

	def kosarajudfs(self, node, visited, adj, count, connected):
		visited[node] = 1
		for i in adj[node]:
			if visited[i] == 0:
				self.kosarajudfs(i, visited, adj, count, connected)
		connected.append(node)

	def dfs(self, node, adj, V, stack, visited):
		visited[node] = 1
		for i in adj[node]:
			if visited[i] == 0:
				self.dfs(i, adj, V, stack, visited)
		stack.append(node)

	def kosaraju(self, V, adj):
		visited = [0] * V
		stack = []
		for i in range(V):
			if visited[i] == 0:
				self.dfs(i, adj, V, stack, visited)
		adjrev = defaultdict(list)
		for i in range(V):
			for conn in adj[i]:
				adjrev[conn].append(i)
		visited1 = [0] * V
		count = 0
		strongly = []
		for i in range(len(stack)):
			ele = stack.pop()
			if visited1[ele] == 0:
				connected = []
				count += 1
				self.kosarajudfs(ele, visited1, adjrev, count, connected)
				strongly.append(connected.copy())
		return count


class Solution:

	def dfs(self, node, stack, visited, adj):
		visited[node] = 1
		for i in adj[node]:
			if visited[i] == 0:
				self.dfs(i, stack, visited, adj)
		stack.append(node)

	def revdfs(self, node, visited, adj):
		visited[node] = 1
		for i in adj[node]:
			if visited[i] == 0:
				self.revdfs(i, visited, adj)

	def kosaraju(self, V, adj):
		visited = [0] * V
		stack = []
		for i in range(V):
			if visited[i] == 0:
				self.dfs(i, stack, visited, adj)
		stack = stack[::-1]
		revadj = [[] for i in range(V)]
		for i in range(V):
			for j in adj[i]:
				revadj[j].append(i)
		visited = [0] * V
		count = 0
		for i in stack:
			if visited[i] == 0:
				self.revdfs(i, visited, revadj)
				count += 1
		return count


class Solution:

	def kosaraju(self, V, adj):
		visited = [False] * V
		stack = []
		for i in range(V):
			if not visited[i]:
				self.dfsUtil(i, adj, visited, stack)
		graphT = self.graphTranspose(adj, V)
		visited = [False] * V
		count = 0
		while stack:
			node = stack.pop()
			if not visited[node]:
				count += 1
				self.dfsUtil2(node, graphT, visited)
		return count

	def dfsUtil(self, u, adj, visited, stack):
		visited[u] = True
		for neighbour in adj[u]:
			if not visited[neighbour]:
				self.dfsUtil(neighbour, adj, visited, stack)
		stack.append(u)

	def graphTranspose(self, adj, V):
		graphT = [[] for _ in range(V)]
		for u in range(V):
			for neighbour in adj[u]:
				graphT[neighbour].append(u)
		return graphT

	def dfsUtil2(self, node, graph, visited):
		visited[node] = True
		for neighbour in graph[node]:
			if not visited[neighbour]:
				self.dfsUtil2(neighbour, graph, visited)


class Solution:

	def kosaraju(self, V, adj):
		l = []
		g2 = dict()
		for i in range(V):
			g2[i] = True

		def dfs(g1, g2, s, l):
			g2[s] = False
			for i in g1[s]:
				if g2[i]:
					dfs(g1, g2, i, l)
			l.append(s)

		def dfs1(g1, g2, s):
			g2[s] = False
			for i in g1[s]:
				if g2[i]:
					dfs1(g1, g2, i)
		for i in range(V):
			if g2[i]:
				dfs(adj, g2, i, l)
		count = 0
		g1 = dict()
		for i in range(V):
			g1[i] = []

		def revGraph(g1, adj):
			for i in range(len(adj)):
				for j in adj[i]:
					if g1.get(j) != None:
						g1[j].append(i)
					if g1.get(j) == None:
						g1[j] = [i]
		revGraph(g1, adj)
		for i in g2.keys():
			g2[i] = True
		while len(l) > 0:
			x = l.pop()
			if g2[x] == False:
				continue
			dfs1(g1, g2, x)
			count = count + 1
		return count


class Solution:

	def top(self, node, adj, stack, vis):
		vis[node] = 1
		for i in adj[node]:
			if vis[i] == 0:
				self.top(i, adj, stack, vis)
		stack.append(node)

	def dfs(self, node, adj, stack, vis):
		vis[node] = 1
		for i in adj[node]:
			if vis[i] == 0:
				self.dfs(i, adj, stack, vis)

	def kosaraju(self, V, adj):
		vis = [0] * V
		stack = []
		for i in range(len(vis)):
			if vis[i] == 0:
				self.top(i, adj, stack, vis)
		reverse = [[] for i in range(V)]
		for i in range(V):
			for j in adj[i]:
				reverse[j].append(i)
		vis = [0] * V
		count = 0
		while len(stack) > 0:
			node = stack.pop()
			if vis[node] == 0:
				count += 1
				self.dfs(node, reverse, stack, vis)
		return count


from collections import deque

class Solution:

	def kosaraju(self, V, adj):

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

		def final_dfs(V, visited, adj):
			visited[V] = True
			for i in adj[V]:
				if visited[i] == False:
					visited[i] = True
					final_dfs(i, visited, adj)
		self.stack = deque()
		visited = [False for i in range(V)]
		for i in range(V):
			if visited[i] == False:
				dfs(i, visited)
		new_adj = [[] for i in range(V)]
		for i in range(V):
			for j in adj[i]:
				new_adj[j].append(i)
		visited = [False for i in range(V)]
		count = 0
		while len(self.stack) != 0:
			index = self.stack.pop()
			if visited[index] == False:
				final_dfs(index, visited, new_adj)
				count += 1
		return count


class Solution:

	def dfs(self, adj, node):
		self.vis[node] = 1
		for i in adj[node]:
			if not self.vis[i]:
				self.dfs(adj, i)
				self.topo.append(i)

	def topo_sort(self, V, adj):
		self.vis = [0 for i in range(V)]
		self.topo = []
		for i in range(V):
			if not self.vis[i]:
				self.dfs(adj, i)
				self.topo.append(i)
		return self.topo

	def simple_dfs(self, n, adj):
		self.vis[n] = 1
		for i in adj[n]:
			if not self.vis[i]:
				self.simple_dfs(i, adj)

	def kosaraju(self, V, adj):
		tp = self.topo_sort(V, adj)
		r_adj = [[] for i in range(V)]
		for i in range(V):
			for j in adj[i]:
				r_adj[j].append(i)
		c = 0
		self.vis = [0 for i in range(V)]
		while tp:
			top = tp.pop()
			if not self.vis[top]:
				self.simple_dfs(top, r_adj)
				c += 1
		return c


from collections import deque
from collections import defaultdict

class Solution:

	def exp1(self, visited, st, node, adj):
		visited[node] = True
		for each in adj[node]:
			if visited[each] == False:
				self.exp1(visited, st, each, adj)
		st.append(node)

	def exp2(self, visited, r_adj, node):
		visited[node] = True
		for each in r_adj[node]:
			if visited[each] == False:
				self.exp2(visited, r_adj, each)

	def reverse_graph(self, adj, V):
		adj1 = defaultdict(list)
		for j in range(V):
			for each in adj[j]:
				adj1[each].append(j)
		return adj1

	def kosaraju(self, V, adj):
		visited = [False for i in range(V)]
		st = []
		res = 0
		for i in range(V):
			if visited[i] == False:
				self.exp1(visited, st, i, adj)
		r_adj = self.reverse_graph(adj, V)
		for i in range(V):
			visited[i] = False
		while len(st) > 0:
			a = st.pop()
			if visited[a] == False:
				res += 1
				self.exp2(visited, r_adj, a)
		return res


class Solution:

	def kosaraju(self, V, adj):
		stack = []
		visited = [-1 for i in range(V)]
		for i in range(V):
			if visited[i] == -1:
				self.dfs(V, adj, i, visited, stack)
		adj1 = [[] for i in range(V)]
		for i in range(V):
			for j in adj[i]:
				adj1[j].append(i)
		visited = [-1 for i in range(V)]
		scc = 0
		while len(stack):
			ele = stack.pop()
			if visited[ele] == -1:
				scc += 1
				self.dfs3(V, adj1, ele, visited)
		return scc

	def dfs(self, V, adj, node, visited, stack):
		visited[node] = 1
		for i in adj[node]:
			if visited[i] == -1:
				self.dfs(V, adj, i, visited, stack)
		stack.append(node)

	def dfs3(self, V, adj, node, visited):
		visited[node] = 1
		for i in adj[node]:
			if visited[i] == -1:
				self.dfs3(V, adj, i, visited)


class Solution:

	def kosaraju(self, V, adj):

		def dfs(i):
			vis[i] = 1
			for it in adj[i]:
				if vis[it] == 0:
					dfs(it)
			st.append(i)

		def dfsd(node):
			vis[node] = 1
			for it in adjd[node]:
				if vis[it] == 0:
					dfsd(it)
		vis = [0] * V
		st = []
		for i in range(V):
			if vis[i] == 0:
				dfs(i)
		adjd = [[] for i in range(V)]
		for i in range(V):
			vis[i] = 0
			for it in adj[i]:
				adjd[it].append(i)
		scc = 0
		while len(st) > 0:
			node = st.pop()
			if vis[node] == 0:
				scc += 1
				dfsd(node)
		return scc


from collections import defaultdict

class Solution:

	def kosaraju(self, V, adj):
		topSort = self.topoSort(V, adj)
		transpose = defaultdict(list)
		visited = set()
		for node in range(V):
			for nei in adj[node]:
				transpose[nei].append(node)

		def dfs(node):
			visited.add(node)
			for nei in transpose[node]:
				if nei not in visited:
					dfs(nei)
		components = 0
		for node in topSort:
			if node not in visited:
				components += 1
				dfs(node)
		return components

	def topoSort(self, V, adj):
		visited = set()
		result = []

		def dfs(node):
			visited.add(node)
			for nei in adj[node]:
				if nei not in visited:
					dfs(nei)
			result.append(node)
		for i in range(V):
			if i not in visited:
				dfs(i)
		return result[::-1]


class Solution:

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

		def dfs1(node):
			visited[node] = 1
			for i in adj[node]:
				if visited[i] == 0:
					dfs1(i)
			stack.append(node)
		for i in range(V):
			if visited[i] == 0:
				dfs1(i)
		graph = []
		for i in range(V):
			visited[i] = 0
			graph.append([])
		for i in range(len(adj)):
			for j in adj[i]:
				graph[j].append(i)
		ans = 0

		def dfs2(node):
			visited[node] = 1
			for i in graph[node]:
				if visited[i] == 0:
					dfs2(i)
		while stack:
			i = stack.pop()
			if visited[i] == 0:
				ans += 1
				dfs2(i)
		return ans


def solve(adj, visited, v, ans):
	visited[v] = 1
	for i in adj[v]:
		if visited[i] == 0:
			solve(adj, visited, i, ans)
	ans.append(v)

def sol(adj, visited, node):
	visited[node] = 1
	for i in adj[node]:
		if visited[i] != 1:
			sol(adj, visited, i)

class Solution:

	def kosaraju(self, V, adj):
		visited = [0] * V
		res = []
		for j in range(V):
			if visited[j] == 0:
				solve(adj, visited, j, res)
		rev = [[] for i in range(V)]
		for i in range(V):
			for j in adj[i]:
				rev[j].append(i)
		cnt = 0
		visi = [0] * V
		while len(res):
			v = res.pop()
			if visi[v] == 0:
				cnt += 1
				sol(rev, visi, v)
		return cnt


class Solution:

	def topo_sort(self, node, visited, adj, topo):
		visited[node] = 1
		for nbr in adj[node]:
			if visited[nbr] == 0:
				self.topo_sort(nbr, visited, adj, topo)
		topo.append(node)

	def dfs(self, node, visited, adj):
		visited[node] = 1
		for nbr in adj[node]:
			if visited[nbr] == 0:
				self.dfs(nbr, visited, adj)

	def kosaraju(self, V, adj):
		visited = [0] * V
		topo = []
		for i in range(V):
			if visited[i] == 0:
				self.topo_sort(i, visited, adj, topo)
		adj_t = {i: [] for i in range(V)}
		for (i, nodes) in enumerate(adj):
			visited[i] = 0
			for node in nodes:
				adj_t[node].append(i)
		count = 0
		while len(topo):
			node = topo.pop()
			if visited[node] == 0:
				self.dfs(node, visited, adj_t)
				count += 1
		return count


class Solution:

	def dfs(self, node, stack, adj):
		self.visited[node] = 1
		for nextNode in adj[node]:
			if self.visited[nextNode] == 0:
				self.dfs(nextNode, stack, adj)
		stack.append(node)

	def dfs3(self, node, adjT):
		self.visited[node] = 1
		for nextNode in adjT[node]:
			if self.visited[nextNode] == 0:
				self.dfs3(nextNode, adjT)

	def kosaraju(self, V, adj):
		self.visited = [0] * V
		stack = []
		for i in range(V):
			if self.visited[i] == 0:
				self.dfs(i, stack, adj)
		adjT = [[] for i in range(V)]
		for i in range(V):
			self.visited[i] = 0
			for j in adj[i]:
				adjT[j].append(i)
		scc = 0
		while stack:
			node = stack.pop()
			if self.visited[node] == 0:
				scc += 1
				self.dfs3(node, adjT)
		return scc


def dfs(vis, adj, node, stack):
	vis[node] = 1
	for i in adj[node]:
		if vis[i] == 0:
			dfs(vis, adj, i, stack)
	stack.append(node)

def dfsnew(node, vis, adj):
	vis[node] = 1
	for i in adj[node]:
		if vis[i] == 0:
			dfsnew(i, vis, adj)

class Solution:

	def kosaraju(self, V, adj):
		vis = [0 for i in range(V)]
		stack = []
		for i in range(V):
			if vis[i] == 0:
				dfs(vis, adj, i, stack)
		transpose = [[] for i in range(V)]
		for i in range(V):
			for j in adj[i]:
				transpose[j].append(i)
		count = 0
		visited = [0 for i in range(V)]
		for i in range(V):
			val = stack.pop()
			if visited[val] == 0:
				count += 1
				dfsnew(val, visited, transpose)
		return count


from typing import List

class Solution:

	def kosaraju(self, V: int, adj: List[List[int]]) -> int:

		def dfs(v, visited, stack):
			visited[v] = True
			for neighbor in adj[v]:
				if not visited[neighbor]:
					dfs(neighbor, visited, stack)
			stack.append(v)

		def dfs_transpose(v, visited, transpose_adj):
			visited[v] = True
			for neighbor in transpose_adj[v]:
				if not visited[neighbor]:
					dfs_transpose(neighbor, visited, transpose_adj)
		visited = [False] * V
		stack = []
		for i in range(V):
			if not visited[i]:
				dfs(i, visited, stack)
		transpose_adj = [[] for _ in range(V)]
		for v in range(V):
			for neighbor in adj[v]:
				transpose_adj[neighbor].append(v)
		visited = [False] * V
		scc_count = 0
		while stack:
			v = stack.pop()
			if not visited[v]:
				dfs_transpose(v, visited, transpose_adj)
				scc_count += 1
		return scc_count


class Solution:

	def kosaraju(self, V, adj):
		visited = [False] * V
		ans = []

		def dfs(u, adj):
			visited[u] = True
			for v in adj[u]:
				if visited[v] == False:
					dfs(v, adj)
			ans.insert(0, u)
		for u in range(V):
			if visited[u] == False:
				dfs(u, adj)
		reverse_adj = [[] for i in range(V)]
		for u in range(V):
			for v in adj[u]:
				reverse_adj[v].append(u)
		visited = [False] * V
		fin = 0

		def dfs1(u, adj):
			visited[u] = True
			for v in adj[u]:
				if visited[v] == False:
					dfs1(v, adj)
		for i in range(V):
			u = ans[i]
			if visited[u] == False:
				fin += 1
				dfs1(u, reverse_adj)
		return fin


class Solution:

	def toposort(self, vertex, visited, adj, topo):
		visited[vertex] = 1
		for nbr in adj[vertex]:
			if visited[nbr] == 0:
				self.toposort(nbr, visited, adj, topo)
		topo.append(vertex)

	def dfs(self, vertex, visited, adj):
		visited[vertex] = 1
		for nbr in adj[vertex]:
			if visited[nbr] == 0:
				self.dfs(nbr, visited, adj)

	def kosaraju(self, V, adj):
		visited = [0] * V
		topo = []
		for i in range(V):
			if visited[i] == 0:
				self.toposort(i, visited, adj, topo)
		adj_t = {i: [] for i in range(V)}
		for (idx, v) in enumerate(adj):
			visited[idx] = 0
			for x in v:
				adj_t[x].append(idx)
		count = 0
		while len(topo):
			x = topo.pop()
			if visited[x] == 0:
				self.dfs(x, visited, adj_t)
				count += 1
		return count


class Solution:

	def kosaraju(self, V, adj):
		ans = 0
		vis = []
		topovis = []
		topostack = []
		transpose = []
		for i in range(V):
			vis.append(0)
			topovis.append(0)

		def dfsTopo(node):
			topovis[node] = 1
			for i in adj[node]:
				if topovis[i] == 0:
					dfsTopo(i)
			topostack.append(node)
			return

		def dfsTvs(node):
			vis[node] = 1
			for i in transpose[node]:
				if vis[i] == 0:
					dfsTvs(i)
			return
		for i in range(V):
			if topovis[i] == 0:
				dfsTopo(i)
		for i in range(V):
			transpose.append([])
		for i in range(len(adj)):
			for j in adj[i]:
				transpose[j].append(i)
		while len(topostack) > 0:
			node = topostack.pop()
			if vis[node] == 0:
				ans += 1
				dfsTvs(node)
		return ans


from collections import defaultdict

class Solution:

	def kosaraju(self, V, adj):
		count = 0
		stack = []
		vis = [False] * V

		def dfs(num):
			for i in adj[num]:
				if vis[i] != True:
					vis[i] = True
					dfs(i)
			stack.append(num)
		for i in range(V):
			if vis[i] != True:
				vis[i] = True
				dfs(i)
		d = defaultdict(list)
		for i in range(V):
			for j in adj[i]:
				d[j].append(i)

		def dfs2(num):
			for i in d[num]:
				if vis[i] != True:
					vis[i] = True
					dfs2(i)
		vis = [False] * V
		while stack:
			i = stack.pop()
			if vis[i] != True:
				vis[i] = True
				dfs2(i)
				count += 1
		return count


def dfs(node, adj, stack, visited):
	visited[node] = 1
	for new_node in adj[node]:
		if visited[new_node] == 0:
			dfs(new_node, adj, stack, visited)
	stack.append(node)

def newDfs(node, transpose, visited):
	visited[node] = 1
	for u in transpose[node]:
		if visited[u] == 0:
			newDfs(u, transpose, visited)

class Solution:

	def kosaraju(self, V, adj):
		visited = [0 for i in range(V)]
		stack = []
		cnt = 0
		for i in range(V):
			if visited[i] == 0:
				dfs(i, adj, stack, visited)
		transpose = {}
		for i in range(V):
			visited[i] = 0
			if i not in transpose:
				transpose[i] = []
			for u in adj[i]:
				if u in transpose:
					transpose[u].append(i)
				else:
					transpose[u] = [i]
		while stack:
			i = stack.pop()
			if visited[i] == 0:
				newDfs(i, transpose, visited)
				cnt += 1
		return cnt


class Solution:

	def compute_finishing_nodes(self, v: int, adj, visited, st):
		visited[v] = True
		for neighbor in adj[v]:
			if visited[neighbor] is False:
				self.compute_finishing_nodes(neighbor, adj, visited, st)
		st.append(v)

	def dfs(self, v: int, adj, visited):
		visited[v] = True
		for neighbor in adj[v]:
			if visited[neighbor] is False:
				self.dfs(neighbor, adj, visited)

	def kosaraju(self, V, adj):
		visited = [False] * V
		st = []
		for v in range(V):
			if visited[v] is False:
				self.compute_finishing_nodes(v, adj, visited, st)
		adj_transpose = [[] for _ in range(V)]
		for v in range(V):
			visited[v] = False
			for u in adj[v]:
				adj_transpose[u].append(v)
		scc = 0
		while len(st) != 0:
			node = st.pop()
			if visited[node] is False:
				scc += 1
				self.dfs(node, adj_transpose, visited)
		return scc


class Solution:

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

	def dfs_dup(self, visited, i, adjT):
		visited[i] = True
		for it in adjT[i]:
			if not visited[it]:
				self.dfs_dup(visited, it, adjT)

	def kosaraju(self, V, adj):
		visited = [False] * V
		stack = []
		for i in range(V):
			if not visited[i]:
				self.dfs(visited, stack, i, adj)
		reverse = [[] for i in range(V)]
		for i in range(V):
			visited[i] = False
			for it in adj[i]:
				reverse[it].append(i)
		scc_count = 0
		while stack:
			node = stack.pop()
			if not visited[node]:
				scc_count += 1
				self.dfs_dup(visited, node, reverse)
		return scc_count


from collections import deque

class Solution:

	def kosaraju(self, V, adj):
		visited_list = ['w' for _ in range(V)]
		end_que = deque()
		for i in range(V):
			if visited_list[i] == 'w':
				result = self.solve(i, adj, visited_list)
				end_que.extend(result)
		rev_adj = self.reverse_edges(adj)
		visited_list = ['w' for _ in range(V)]
		scc_list = []
		while len(end_que) > 0:
			proc_node = end_que.pop()
			if visited_list[proc_node] == 'w':
				output = self.solve(proc_node, rev_adj, visited_list)
				scc_list.append(list(output))
		return len(scc_list)

	def solve(self, vert, adj, visited_list):
		output = deque()
		visited_list[vert] = 'g'
		for s in adj[vert]:
			if visited_list[s] == 'w':
				result = self.solve(s, adj, visited_list)
				output.extend(result)
		output.append(vert)
		return output

	def reverse_edges(self, matrix):
		n_row = len(matrix)
		re_matrix = [[] for _ in range(n_row)]
		for (i, neighbourhood) in enumerate(matrix):
			for s in neighbourhood:
				re_matrix[s].append(i)
		return re_matrix


class Solution:

	def kosaraju(self, V, adj):
		visited = set()
		stack = []

		def dfs(node):
			visited.add(node)
			for it in adj[node]:
				if it not in visited:
					dfs(it)
			stack.append(node)

		def dfs3(node):
			visited.add(node)
			for it in adjT[node]:
				if it not in visited:
					dfs3(it)
		for i in range(V):
			if i not in visited:
				dfs(i)
		adjT = [[] for _ in range(V)]
		for i in range(V):
			visited.discard(i)
			for it in adj[i]:
				adjT[it].append(i)
		scc = 0
		while stack:
			ele = stack.pop()
			if ele not in visited:
				scc += 1
				dfs3(ele)
		return scc


from collections import defaultdict

class Solution:

	def kosaraju(self, V, adj):
		result = []
		original_graph = self.buildGraph(adj)
		stack = []
		visited_vertex = [False] * V
		for i in range(V):
			if not visited_vertex[i]:
				self.dfsOnOriginalgraph(i, visited_vertex, stack, original_graph)
		gr = self.reverseGraph(V, original_graph)
		visited_vertex = [False] * V
		while stack:
			i = stack.pop()
			if not visited_vertex[i]:
				result.append(self.dfsOnReverseGraph(i, visited_vertex, list(gr.values())))
		return len(result)

	def dfsOnOriginalgraph(self, d, visited_vertex, stack, original_graph):
		visited_vertex[d] = True
		for i in original_graph[d]:
			if not visited_vertex[i]:
				self.dfsOnOriginalgraph(i, visited_vertex, stack, original_graph)
		stack = stack.append(d)

	def dfsOnReverseGraph(self, d, visited_vertex, gr):
		temp = []
		visited_vertex[d] = True
		for i in gr[d]:
			if not visited_vertex[i]:
				self.dfsOnReverseGraph(i, visited_vertex, gr)
		return d

	def reverseGraph(self, V, adj):
		reverse_graph = defaultdict(list)
		for i in range(V):
			for j in adj[i]:
				if j not in reverse_graph:
					reverse_graph[j] = [i]
				else:
					reverse_graph[j].append(i)
		for i in range(V):
			if i not in reverse_graph:
				reverse_graph[i] = []
		return {k: v for (k, v) in sorted(reverse_graph.items(), key=lambda x: x[0])}

	def buildGraph(self, adj):
		graph = {}
		for (i, j) in enumerate(adj):
			graph[i] = j
		return graph


class Solution:

	def kosaraju(self, V, adj):
		stack = []
		visited = [False for i in range(V)]
		for i in range(0, V):
			if visited[i] == False:
				self.dfs(i, adj, visited, stack)
		new_graph = [[] for i in range(V)]
		for i in range(0, V):
			for x in adj[i]:
				new_graph[x].append(i)
		visited = [False for i in range(V)]
		ans = 0
		while len(stack) != 0:
			v = stack.pop()
			if visited[v] == False:
				self.new_dfs(v, new_graph, visited)
				ans += 1
		return ans

	def dfs(self, v, adj, visited, stack):
		visited[v] = True
		for x in adj[v]:
			if visited[x] == False:
				self.dfs(x, adj, visited, stack)
		stack.append(v)

	def new_dfs(self, v, new_graph, visited):
		visited[v] = True
		for x in new_graph[v]:
			if visited[x] == False:
				self.new_dfs(x, new_graph, visited)


class Solution:

	def kosaraju(self, n, adj):
		stack = []
		seen = [False] * n

		def dfs1(u):
			seen[u] = True
			for v in adj[u]:
				if not seen[v]:
					dfs1(v)
			stack.append(u)

		def dfs2(u):
			seen[u] = True
			for v in radj[u]:
				if not seen[v]:
					dfs2(v)
		for u in range(n):
			if not seen[u]:
				dfs1(u)
		radj = [[] for _ in range(n)]
		for u in range(n):
			seen[u] = False
			for v in adj[u]:
				radj[v].append(u)
		scc = 0
		while stack:
			u = stack.pop()
			if not seen[u]:
				scc += 1
				dfs2(u)
		return scc


class Solution:

	def kosaraju(self, V, adj):

		def dfs1(node, visited, adj, stack):
			visited[node] = True
			neighbours = adj[node]
			for n in neighbours:
				if not visited[n]:
					dfs1(n, visited, adj, stack)
			stack.append(node)

		def dfs2(node, visited, adj):
			visited[node] = True
			neighbours = adj[node]
			for n in neighbours:
				if not visited[n]:
					dfs2(n, visited, adj)

		def reverseGraph(adj, V):
			adjR = [[] for _ in range(V)]
			for node in range(V):
				for n in adj[node]:
					adjR[n].append(node)
			return adjR
		stack = []
		visited = [False for _ in range(V)]
		for node in range(V):
			if not visited[node]:
				dfs1(node, visited, adj, stack)
		adjR = reverseGraph(adj, V)
		visited = [False for _ in range(V)]
		scc = 0
		for node in reversed(stack):
			if not visited[node]:
				scc += 1
				dfs2(node, visited, adjR)
		return scc