In: Computer Science
First of all you want the number of connected components in directed graph G. Right?
I am assuming that you don't want the strongly connected components(which usually asked in directed graph).
Which implies that you just want the connected components in a graph G. Which is same in directed and undirected graph.
Below is the well documented code -
from collections import defaultdict
def dfs(src):
# This is our base condition for stoping the recusrion
# If src in taken, then it means that we've already processed it.
if src in taken:
return
# Now we've processed src vertex so we will add it to taken set
taken.add(src)
# Now calling dfs for all the vertices connected to src(if any) vertex because all of them are in the same component.
for des in adj[src]:
dfs(des)
# Here n is the number of vertices and m is the total number of edges
n, m = map(int, input().split())
# Here we assigned a defaultdict(key : value[set]) object to adj
adj = defaultdict(set)
# taking all m edges
for _ in range(m):
a, b = map(int, input().split())
# Below line simply means there is a path from a to b
adj[a].add(b)
# Below line simply means there is a path from b to a
adj[b].add(a)
# taken set contains all the visited vertices
taken = set()
# connected_components is the total number of connected components
connected_components = 0
# Checking from each vertices
for src in range(1, n + 1):
# If src vertex is in taken then it means we've already consider it in a different component, hence we'll not process it this time
if src not in taken:
dfs(src)
# For each src that is not in taken we will add 1 to connected_components, because it means src is the vertex of that component which we haven't discovered untill now.
connected_components += 1
# Printing the total number of connected components
print(connected_components)
Time Complexity -
O(|V| + |E|), Because we are processing vertices and edges in linear time.
Sample Input -
8 6
1 3
1 2
1 4
6 7
8 5
2 4
Sample Output -
3