Challenge: Count the Groups

Lab C++ Intermediate 20 points

Print how many separate groups of places there are (a place with no roads is its own group).

Input

Line 1: n m – places numbered 0 to n − 1 and m roads. Then m lines a b: a two-way road between a and b.

Output

The number of groups.

Example

Input

Output

Sample input available Sample output available

Editor

C++

Hints

Each unseen place starts a new group.

From it, DFS/BFS marks the whole group as seen.

Solution explanation

O(V + E). An explicit stack avoids deep recursion on big graphs.

Show solution

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n, m;
    cin >> n >> m;
    vector<vector<int>> g(n);
    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    vector<bool> seen(n, false);
    int groups = 0;
    for (int s = 0; s < n; s++) {
        if (seen[s]) continue;
        groups++;
        vector<int> stack = {s};
        seen[s] = true;
        while (!stack.empty()) {
            int v = stack.back();
            stack.pop_back();
            for (int w : g[v])
                if (!seen[w]) { seen[w] = true; stack.push_back(w); }
        }
    }
    cout << groups << endl;
    return 0;
}

Output

Answer