Step 3 of 6
Depth-first flood fill
Depth-first search follows one path as far as it can before backtracking. It's the natural tool for "which things are connected?": pick an unvisited vertex, DFS from it to mark its whole component, and count how many times you had to start.
Recursive DFS is elegant, but a big component can overflow the call stack (the default stack is only about 1 MB, and on this site even less). Production code often uses an explicit stack instead:
std::vector<std::pair<int, int>> stack = {{r, c}};
while (!stack.empty()) { auto [r, c] = stack.back(); stack.pop_back(); ... push neighbors ... }
Your turn: write int count_islands(std::vector<std::string> grid), counting groups of # cells connected up/down/left/right. Use an explicit stack: the test has an island of 250,000 cells.