Given an undirected graph $G$ with $n$ nodes and $m$ edges. We are required to find in it all the connected components, i.e, several groups of vertices such that within a group each vertex can be reached from another and no path exists between different groups.
1. An algorithm for solving the problem
- To solve the problem, we can use Depth First Search or Breadth First Search.
- In fact, we will be doing a series of rounds of DFS: The first round will start from first node and all the nodes in the first connected component will be traversed (found). Then we find the first unvisited node of the remaining nodes, and run Depth First Search on it, thus finding a second connected component. And so on, until all the nodes are visited.
- The total asymptotic running time of this algorithm is $O(n + m)$ : In fact, this algorithm will not run on the same vertex twice, which means that each edge will be seen exactly two times (at one end and at the other end).
2. Implementation
int n; vector<int> g[MAXN] ; bool used[MAXN] ; vector<int> comp ; void dfs(int v) { used[v] = true ; comp.push_back(v); for (size_t i = 0; i < (int) g[v].size(); ++i) { int to = g[v][i]; if (!used[to]) dfs(to); } } void find_comps() { for (int i = 0; i < n ; ++i) used [i] = false; for (int i = 0; i < n ; ++i) if (!used[i]) { comp.clear(); dfs(i); cout << "Component:" ; for (size_t j = 0; j < comp.size(); ++j) cout << ' ' << comp[j]; cout << endl ; } }
- The most important function that is used is
find_comps()
which finds and displays connected components of the graph. - The graph is stored in adjacency list representation, i.e
g[i]
contains a list of vertices that have edges from the vertexi
. The constantMAXN
should be set equal to the maximum possible number of vertices in the graph. - Vector
comp
contains a list of nodes in the current connected component.
3. Practice Problems
Related posts:
Sereja and Intervals
Hongcow Buys a Deck of Cards
Andrey and Problem
Ksusha and Square
Aztec Catacombs
Ebony and Ivory
Hostname Aliases
Promocodes with Mistakes
Ordering T-Shirts
Love "A"
Design Tutorial: Make It Nondeterministic
Dream Team
Challenges in school №41
Graph Reconstruction
Petr and a Combination Lock
Primality tests
Strong Orientation
Walk on Matrix
Nastya and Scoreboard
Maximum Distance
Java Program to Check whether Graph is a Bipartite using BFS
Friends
Flowers and Chocolate
Maximum flow - Push-relabel method improved
Definite Game
Restoring Three Numbers
Image Preview
Optimal Polygon Perimeter
Wilbur and Swimming Pool
Treap (Cartesian tree)
Kuhn's Algorithm for Maximum Bipartite Matching
Equalize