An undirected graph has n vertices, numbered 0 to n - 1, and m edges. Count its connected components: groups of vertices that can reach each other along edges. A vertex with no edges is a component on its own.
What to build
A count of the separate groups in a graph, using depth-first search.
Requirements
- Run a depth-first search from each vertex that has not been visited yet.
- Count one component for each search you start.
- A vertex with no edges counts as a component.
Input
The first line has n and m (1 ≤ n ≤ 100, 0 ≤ m ≤ 1000). Each of the next m lines has an edge u v.
Output
The number of connected components.
Constraints
1 ≤ n ≤ 100 and 0 ≤ m ≤ 1000.
Example
Input:
6 3
0 1
1 2
3 4
Output:
3
Why it works
One search visits everything that can be reached from its start, which is exactly one component. So the number of searches started is the number of components.
Examples
6 3 0 1 1 2 3 4
3
3 0
3
Hints
Hint 1
Write a recursive dfs(u) that marks u visited and visits every unvisited neighbour.
Hint 2
Loop over all vertices: each one that is still unvisited starts a new component, so count it and call dfs on it.
Solution
Show one correct solution (try it yourself first)
#include <stdio.h>
int n;
int adj[100][100];
int visited[100];
void dfs(int u) {
visited[u] = 1;
for (int v = 0; v < n; v++)
if (adj[u][v] && !visited[v]) dfs(v);
}
int main(void) {
int m;
scanf("%d %d", &n, &m);
for (int i = 0; i < m; i++) {
int u, v;
scanf("%d %d", &u, &v);
adj[u][v] = adj[v][u] = 1;
}
int components = 0;
for (int u = 0; u < n; u++) {
if (!visited[u]) {
components++;
dfs(u);
}
}
printf("%d\n", components);
return 0;
}