Given a Directed Graph with V vertices and E edges,  Find the members of strongly connected components in the graph.
Example 1:
Input:
Output:
0 1 2,3,4,
Explanation:
We can clearly see that there are 3 Strongly
Connected Components in the Graph as mentioned
in the Output.
Example 2:
Input:
Output:
0 1 2,
Explanation:
All of the nodes are connected to each other.
So, there's only one SCC as shown.
Your Task:
You don't need to read input or print anything. Your task is to complete the function tarjans() which takes the number of vertices V and adjacency list of the graph as input parameters and returns a list of list of integers denoting the members of strongly connected components in the given graph.
Note: A single strongly connected component must be represented in the form of a list if integers sorted in the ascending order. The resulting list should consist of a list of all SCCs which must be sorted in a way such that a lexicographically smaller list of integers appears first. 
Expected Time Complexity: O(V + E).
Expected Auxiliary Space: O(V).
Constraints:
1  ≤  V  ≤  10^{5}
1  ≤  E  ≤  10^{5}
0  ≤  u, v  ≤  N-1

Source: geeksforgeeks | Difficulty: MEDIUM_HARD
Tags: Graph algorithms

Data structures

Starter code: #User function Template for python3

class Solution:
    
    #Function to return a list of lists of integers denoting the members 
    #of strongly connected components in the given graph.
    def tarjans(self, V, adj):
        # code here

Solutions:
class Solution:

	def dfs(self, node, parent, adj, disc, low, stk, in_stk, scc):
		disc[node] = low[node] = self.timer
		self.timer += 1
		stk.append(node)
		in_stk[node] = True
		for nbr in adj[node]:
			if disc[nbr] == -1:
				self.dfs(nbr, node, adj, disc, low, stk, in_stk, scc)
				low[node] = min(low[node], low[nbr])
			elif in_stk[nbr]:
				low[node] = min(low[node], disc[nbr])
		if low[node] == disc[node]:
			temp = []
			u = -1
			while u != node:
				u = stk.pop()
				temp.append(u)
				in_stk[u] = False
			temp.sort()
			scc.append(temp)

	def tarjans(self, V, adj):
		disc = [-1] * V
		low = [-1] * V
		self.timer = 0
		stk = []
		in_stk = [False] * V
		scc = []
		for i in range(V):
			if disc[i] == -1:
				self.dfs(i, -1, adj, disc, low, stk, in_stk, scc)
		scc.sort()
		return scc


from collections import defaultdict

class Solution:

	def tarjans(self, V, adj):

		def helper(node, count):
			if node in visited:
				return count
			visited[node] = 0
			for item in adj[node]:
				count = helper(item, count)
			count += 1
			visited[node] = count
			return count
		count = 0
		visited = {}
		for i in range(V):
			count = helper(i, count)
		nodes = [key for (key, value) in sorted(visited.items(), key=lambda x: -x[1])]
		reversed_adj = defaultdict(list)
		for (target, sources) in enumerate(adj):
			for node in sources:
				reversed_adj[node].append(target)
		output = []
		visited = set()
		for item in nodes:
			if item in visited:
				continue
			temp = set()
			stack = [item]
			while stack:
				node = stack.pop()
				if node in temp or node in visited:
					continue
				temp.add(node)
				stack += reversed_adj[node]
			output.append(sorted(temp))
			visited.update(temp)
		return sorted(output)


class Solution:

	def tarjans(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)
		l2 = []

		def dfs1(g1, g2, s):
			g2[s] = False
			for i in g1[s]:
				if g2[i]:
					dfs1(g1, g2, i)
			l2.append(s)
		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
		l1 = []
		while len(l) > 0:
			x = l.pop()
			if g2[x] == False:
				continue
			dfs1(g1, g2, x)
			k = [i for i in l2]
			k.sort()
			l1.append(k)
			count = count + 1
			l2 = []
		l1.sort()
		return l1


from collections import deque, defaultdict

class Solution:

	def dfs(self, node, adj):
		self.vis[node] = True
		for neib in adj[node]:
			if not self.vis[neib]:
				self.dfs(neib, adj)
		self.stack.append(node)

	def toposort(self, V, adj):
		self.vis = [False] * V
		for node in range(V):
			if not self.vis[node]:
				self.dfs(node, adj)

	def genscc(self, node, adj):
		self.vis[node] = True
		self.tempt.append(node)
		for neib in adj[node]:
			if not self.vis[neib]:
				self.genscc(neib, adj)

	def transpose(self, V, adj):
		tp = defaultdict(list)
		for node in range(V):
			for neib in adj[node]:
				tp[neib].append(node)
		return tp

	def tarjans(self, V, adj):
		self.stack = []
		self.tempt = []
		self.arr = []
		self.toposort(V, adj)
		self.vis = [False] * V
		self.dfsvis = [False] * V
		self.stack = self.stack[::-1]
		adj = self.transpose(V, adj)
		for node in self.stack:
			if not self.vis[node]:
				self.tempt = []
				self.genscc(node, adj)
				self.tempt.sort()
				self.arr.append(self.tempt)
		self.arr.sort()
		return self.arr


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

def dfs2(node, transpose, visited, temp):
	visited[node] = 1
	temp.append(node)
	for u in transpose[node]:
		if visited[u] == 0:
			dfs2(u, transpose, visited, temp)

class Solution:

	def tarjans(self, V, adj):
		visited = [0 for i in range(V)]
		stack = []
		for i in range(V):
			if visited[i] == 0:
				dfs1(i, adj, stack, visited)
		transpose = {}
		for i in range(V):
			visited[i] = 0
			if i not in transpose:
				transpose[i] = []
			for j in adj[i]:
				if j in transpose:
					transpose[j].append(i)
				else:
					transpose[j] = [i]
		temp = []
		ans = []
		while stack:
			node = stack.pop()
			if visited[node] == 0:
				temp = []
				dfs2(node, transpose, visited, temp)
				temp.sort()
				ans.append(temp)
		ans.sort()
		return ans


class Solution:
	ans = []
	temp = []
	Time = 0

	def SCCUtil(self, adj, u, low, disc, stackMember, st):
		disc[u] = self.Time
		low[u] = self.Time
		self.Time += 1
		stackMember[u] = True
		st.append(u)
		for v in adj[u]:
			if disc[v] == -1:
				self.SCCUtil(adj, v, low, disc, stackMember, st)
				low[u] = min(low[u], low[v])
			elif stackMember[v] == True:
				low[u] = min(low[u], disc[v])
		w = -1
		if low[u] == disc[u]:
			while w != u:
				w = st.pop()
				self.temp.append(w)
				stackMember[w] = False
			self.ans.append(self.temp)
			self.temp = []

	def tarjans(self, V, adj):
		self.ans = []
		self.temp = []
		disc = [-1] * V
		low = [-1] * V
		stackMember = [False] * V
		st = []
		for i in range(V):
			if disc[i] == -1:
				self.SCCUtil(adj, i, low, disc, stackMember, st)
		for j in range(len(self.ans)):
			self.ans[j].sort()
		self.ans.sort()
		return self.ans


class Solution:

	def tarjans(self, V, adj):
		stack = []
		visit = [0] * V

		def fun(i):
			visit[i] = 1
			for j in adj[i]:
				if visit[j] == 0:
					fun(j)
			stack.append(i)
		for i in range(V):
			if visit[i] == 0:
				fun(i)
		ans = []
		visit = [0] * V
		new = [[] for _ in range(V)]
		for i in range(V):
			for k in adj[i]:
				new[k].append(i)

		def fun1(i, lis):
			visit[i] = 1
			lis.append(i)
			for j in new[i]:
				if visit[j] == 0:
					fun1(j, lis)
			return lis
		while stack:
			t = stack.pop()
			if visit[t] == 0:
				l = fun1(t, [])
				l.sort()
				ans.append(l)
		ans.sort()
		return ans


class Solution:

	def tarjans(self, V, adj):

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

		def revdfs(node, vis, adj, temp):
			vis[node] = 1
			temp.append(node)
			for j in adj[node]:
				if vis[j] == 0:
					revdfs(j, vis, adj, temp)
		vis = [0] * V
		st = []
		for i in range(V):
			if vis[i] == 0:
				topo(i, vis, adj, st)
		reverse_adj = [[] for _ in range(V)]
		for i in range(V):
			for j in adj[i]:
				reverse_adj[j].append(i)
		vis = [0] * V
		res = []
		while st:
			temp = []
			node = st.pop()
			if vis[node] == 0:
				revdfs(node, vis, reverse_adj, temp)
				temp.sort()
				res.append(temp)
		res.sort()
		return res


from collections import defaultdict

class Solution:

	def tarjans(self, n, adjList):
		(lowArr, timeOfVisitArr, time) = ([1000000000.0 for _ in range(n)], [1000000000.0 for _ in range(n)], 0)
		(stack, inStack, listOfStronglyConnectedComponents) = ([], [False for _ in range(n)], [])

		def dfs(node):
			nonlocal lowArr, timeOfVisitArr, time, stack, listOfStronglyConnectedComponents
			lowArr[node] = time
			timeOfVisitArr[node] = time
			time += 1
			stack.append(node)
			inStack[node] = True
			for neigh in adjList[node]:
				if lowArr[neigh] == 1000000000.0:
					dfs(neigh)
				if inStack[neigh]:
					lowArr[node] = min(lowArr[node], lowArr[neigh])
			if lowArr[node] == timeOfVisitArr[node]:
				while True:
					componentNode = stack.pop()
					inStack[componentNode] = False
					lowArr[componentNode] = lowArr[node]
					if componentNode == node:
						break
		for node in range(n):
			if lowArr[node] == 1000000000.0:
				dfs(node)
		mapOfComponents = defaultdict(list)
		for (node, componentIndex) in enumerate(lowArr):
			mapOfComponents[componentIndex].append(node)
		for stronglyConnectedComponentNodes in mapOfComponents.values():
			listOfStronglyConnectedComponents.append(sorted(stronglyConnectedComponentNodes))
		return sorted(listOfStronglyConnectedComponents)


class Solution:

	def tarjans(self, n, adjList):
		revAdjList = [[] for _ in range(n)]
		for node in range(n):
			for neigh in adjList[node]:
				revAdjList[neigh].append(node)
		stack = []
		visited = set()

		def dfs(node):
			nonlocal visited
			visited.add(node)
			for neigh in adjList[node]:
				if neigh not in visited:
					dfs(neigh)
			stack.append(node)
		for node in range(n):
			if node not in visited:
				dfs(node)
		visited2 = set()

		def dfs2(node, componentNodes):
			nonlocal visited2
			visited2.add(node)
			componentNodes.add(node)
			for neigh in revAdjList[node]:
				if neigh not in visited2:
					dfs2(neigh, componentNodes)
			return componentNodes
		listOfStronglyConnectedComponents = []
		for node in reversed(stack):
			if node not in visited2:
				listOfStronglyConnectedComponents.append(sorted(dfs2(node, set())))
		return sorted(listOfStronglyConnectedComponents)


class Solution:

	def tarjans(self, V, adj):
		conn = []
		dfs_member = [False for _ in range(V)]
		stack = []
		d_time = [-1 for _ in range(V)]
		low_val = [-1 for _ in range(V)]
		timer = [1]
		for i in range(V):
			if d_time[i] == -1:
				self.tarjan(adj, i, d_time, low_val, timer, stack, dfs_member, conn)
		return sorted(conn)

	def tarjan(self, graph, ver, d_time, low_val, timer, stack, dfs_mem, conn):
		d_time[ver] = timer[0]
		low_val[ver] = timer[0]
		timer[0] += 1
		stack.append(ver)
		dfs_mem[ver] = True
		for adj in graph[ver]:
			if d_time[adj] == -1:
				self.tarjan(graph, adj, d_time, low_val, timer, stack, dfs_mem, conn)
				low_val[ver] = min(low_val[ver], low_val[adj])
			elif dfs_mem[adj]:
				low_val[ver] = min(low_val[ver], d_time[adj])
		if low_val[ver] == d_time[ver]:
			c = []
			while stack[-1] != ver:
				item = stack.pop()
				dfs_mem[item] = False
				c.append(item)
			c.append(stack.pop())
			dfs_mem[ver] = False
			conn.append(sorted(c))


class Solution:

	def tarjans(self, n, adj):
		(dis, low, vis, self.time, self.result, stack) = ([0] * n, [0] * n, [0] * n, 0, [], [])

		def dfs(source):
			dis[source] = low[source] = self.time
			self.time += 1
			stack.append(source)
			vis[source] = 1
			for child in adj[source]:
				if vis[child] == 0:
					dfs(child)
					low[source] = min(low[source], low[child])
				elif vis[child] == 1:
					low[source] = min(low[source], dis[child])
			if low[source] == dis[source]:
				self.result.insert(0, [])
				while stack[-1] != source:
					vis[stack[-1]] = 2
					self.result[0].insert(0, stack.pop())
				self.result[0].insert(0, stack.pop())
				self.result[0].sort()
				vis[source] = 2
		for i in range(n):
			if vis[i] == 0:
				dfs(i)
		return sorted(self.result)


class Solution:

	def DFS(self, adj, i, a, f, t):
		a[i] = t
		for j in adj[i]:
			if j not in a:
				t = self.DFS(adj, j, a, f, t + 1)
		t += 1
		f[i] = t
		return t

	def tarjans(self, V, adj):
		adj_T = [[] for i in range(V)]
		for i in range(V):
			for j in adj[i]:
				adj_T[j].append(i)
		(a, f, t) = ({}, OrderedDict(), 0)
		for i in range(V):
			if i not in a:
				self.DFS(adj, i, a, f, t)
		f = OrderedDict(reversed(list(f.items())))
		(d, ans) = ({}, [])
		for j in f:
			if j not in d:
				(d[j], Q) = (True, [j])
				ans.append([])
				while len(Q) > 0:
					a = Q.pop(0)
					ans[-1].append(a)
					for i in adj_T[a]:
						if i not in d:
							d[i] = True
							Q.append(i)
				ans[-1].sort()
		ans.sort()
		return ans


class Solution:

	def __init__(self):
		self.time = 0
		self.sccs = []

	def findComponents(self, u, adj, disc, lowLink, stack, stackItem):
		self.time += 1
		lowLink[u] = self.time
		disc[u] = self.time
		stackItem[u] = True
		stack.append(u)
		for v in adj[u]:
			if disc[v] == -1:
				self.findComponents(v, adj, disc, lowLink, stack, stackItem)
				lowLink[u] = min(lowLink[u], lowLink[v])
			elif stackItem[v]:
				lowLink[u] = min(lowLink[u], lowLink[v])
		if lowLink[u] == disc[u]:
			scc = []
			poppedItem = 0
			while stack[-1] != u:
				poppedItem = stack[-1]
				scc.append(poppedItem)
				stackItem[poppedItem] = False
				stack.pop()
			poppedItem = stack[-1]
			scc.append(poppedItem)
			stackItem[poppedItem] = False
			stack.pop()
			scc.sort()
			self.sccs.append(scc)

	def tarjans(self, V, adj):
		disc = [-1] * V
		lowLink = [-1] * V
		stackItem = [False] * V
		stack = []
		for node in range(V):
			if disc[node] == -1:
				self.findComponents(node, adj, disc, lowLink, stack, stackItem)
		self.sccs.sort()
		return self.sccs


class Solution:

	def tarjans(self, V, adj):
		stack = []
		visited = [0] * V
		ans = []
		for i in range(0, V):
			if visited[i] == 0:
				self.dfs(i, visited, adj, stack)
		adjrev = [[] for i in range(V)]
		for i in range(0, V):
			visited[i] = 0
			for ele in adj[i]:
				adjrev[ele].append(i)
		while len(stack) > 0:
			ele = stack[-1]
			stack.pop()
			if visited[ele] == 0:
				temp = []
				self.helper(ele, visited, adjrev, temp)
				temp.sort()
				ans.append(temp)
		ans.sort()
		return ans

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

	def helper(self, node, visited, adjrev, temp):
		visited[node] = 1
		temp.append(node)
		for neigh in adjrev[node]:
			if visited[neigh] == 0:
				self.helper(neigh, visited, adjrev, temp)