A weakly connected graph is a directed graph in which there exists a path between every pair of nodes, regardless of the direction of the edges. In other words, if the graph was undirected, it would be a connected graph. However, in a directed graph, connectivity is more complex as it depends on the direction of the edges, and a weakly connected graph can have nodes that are only reachable in one direction.
In a directed graph, weakly connected components are subsets of nodes where each node can be reached from any other node by following edges in any direction. Understanding weakly connected components is important in analyzing the structure of a graph and can have practical applications in various fields such as social network analysis and transportation planning. In this article, we will look in more detail about this topic.
Problem
Given a directed graph G, find all the weakly connected components in G. A weakly connected component is a subgraph of a directed graph in which all vertices are connected by some path, irrespective of edge direction.
Weakly Connected: A directed graph G is weakly connected if it lacks a directed path (from u to v or v to u for any pair of vertices u, v).
In other words, draw an undirected graph G` of G whose edges are obtained by removing the arrowheads from the edges in G and making them bidirectional. If G` is connected, we can say that G is weakly connected.
In a connected graph, each node is reachable from every other node. |
Input:
- An integer n represents the number of vertices in the graph.
- An integer k represents the size of the adjacency list.
- An array G represents the adjacency list.
Output: Print all the weakly connected components of the given graph in separate lines.
Alert Ninjas: Don’t stop now! Enroll in the Competitive Programming course today. Learn the art of writing efficient code and compete in code competitions worldwide.
For Example,
Input: N = 7, k = 6, G = {{0,1}, {1,2}, {2,3}, {3,4}, {4,0}, {5,6}}.
In the above given directed graph G, let’s draw its corresponding undirected graph whose edges are obtained by removing the arrowheads from the edges in G and making them bidirectional.
Both the components of the above-undirected Graph are connected; therefore, these two are weakly connected components of the input directed Graph.
Output: [0, 1, 2, 3, 4]
[5, 6]
Recommended: Try to solve it yourself before moving on to the solution.