check_digraph_strongly_connected.py

from collections import defaultdict

class Graph:
	def __init__(self,v):
		self.v = v
		self.graph = defaultdict(list)

	def add_edge(self,u,v):
		self.graph[u].append(v)

	def dfs(self):
		visited = [False] * self.v
		self.dfs_util(0,visited)
		if visited == [True]*self.v:
			return True
		return False

	def dfs_util(self,i,visited):
		visited[i] = True
		for u in self.graph[i]:
			if not(visited[u]):
				self.dfs_util(u,visited)

	def reverse_graph(self):
		g = Graph(self.v)
		for i in range(len(self.graph)):
			for j in self.graph[i]:
				g.add_edge(j,i)
		return g


	def is_sc(self):
		if self.dfs():
			gr = self.reverse_graph()
			if gr.dfs():
				return True
		return False


g1 = Graph(5)
g1.add_edge(0, 1)
g1.add_edge(1, 2)
g1.add_edge(2, 3)
g1.add_edge(3, 0)
g1.add_edge(2, 4)
g1.add_edge(4, 2)
print ("Yes") if g1.is_sc() else print("No")
 
g2 = Graph(4)
g2.add_edge(0, 1)
g2.add_edge(1, 2)
g2.add_edge(2, 3)
print ("Yes") if g2.is_sc() else print("No")