Depth-First Search and Connected Pieces

Go deep, then backtrack

DFS follows one path as far as possible, then backs up and tries the next branch. Recursion does this naturally.

Think of it like this: Exploring a maze: keep walking until a dead end, then return to the last junction and try another way.

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

vector<vector<int>> g;
vector<bool> seen;

void dfs(int v) {
    seen[v] = true;
    for (int w : g[v])
        if (!seen[w]) dfs(w);
}

int main() {
    int n = 7;
    g.assign(n, {});
    seen.assign(n, false);
    for (auto [a, b] : vector<pair<int, int>>{{0, 1}, {1, 2}, {3, 4}}) {
        g[a].push_back(b);
        g[b].push_back(a);
    }
    int groups = 0;
    for (int v = 0; v < n; v++) {
        if (!seen[v]) {
            groups++;               // a new connected component
            dfs(v);
        }
    }
    cout << "groups: " << groups << endl;     // {0,1,2} {3,4} {5} {6}
    return 0;
}

Output

groups: 4

Grids are graphs too

Each cell is a vertex; up/down/left/right neighbours are edges. Counting islands of #:

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

vector<string> grid = {"##..#", "#...#", "..#..", "....."};
int R = 4, C = 5;

void sink(int r, int c) {
    if (r < 0 || r >= R || c < 0 || c >= C || grid[r][c] != '#') return;
    grid[r][c] = '.';                         // mark visited by sinking it
    sink(r + 1, c); sink(r - 1, c); sink(r, c + 1); sink(r, c - 1);
}

int main() {
    int islands = 0;
    for (int r = 0; r < R; r++)
        for (int c = 0; c < C; c++)
            if (grid[r][c] == '#') { islands++; sink(r, c); }
    cout << "islands: " << islands << endl;
    return 0;
}

Output

islands: 3