Why this matters
Some maps change over time. A flood map gets new wet cells as the water spreads. A game world reveals new tiles as the player walks. A scanned satellite image gets new land cells as more of it arrives. Each time a cell changes, a program may need to answer one question: how many separate pieces of land are there now?
The simplest answer is to count again from scratch after every change. That works for a small map, but it repeats the same work many times. This lesson shows a faster method. It keeps track of which land cells already touch, and it updates the count each time a new cell arrives.
The lesson on island counting with flood fill, earlier in this module, counts islands on a fixed grid. Flood fill is a search that starts at one land cell and visits every land cell it can reach. That lesson assumes the grid is complete before counting starts. Here the grid grows one cell at a time, so the method has to be different.
The tool for the job is union-find, also called a disjoint set. It keeps a collection of groups, can tell whether two items are in the same group, and can merge two groups into one. The same tool appears in the lessons on Kruskal's algorithm and on union-find deeper.
The problem in plain words
We have a grid with rows rows and cols columns. At the start, every cell is water. We receive a list of positions. Each position names a cell that becomes land. After each position, we report how many islands exist.
A cell is named by its row and column. Rows and columns both start at 0. The cell (0, 2) is in row 0 and column 2. We write it as a pair of numbers in the code, not as text.
An island is a group of land cells that connect through their sides. Two land cells are connected when they are next to each other up, down, left or right. Two land cells that only touch at a corner are not connected. Each cell has up to four neighbours (the cells directly up, down, left and right of it). A cell on the edge of the grid has fewer.
Here is a grid with 3 rows and 3 columns. The letter L is land and the dot is water. The positions arrive in the order 0,0 then 0,1 then 1,2 then 2,1.
after (0,0) after (0,1) after (1,2) after (2,1)
L . . L L . L L . L L .
. . . . . . . . L . . L
. . . . . . . . . . L .
islands: 1 islands: 1 islands: 2 islands: 3The answer for this list is 1, 1, 2, 3. After the second position the two land cells touch, so they form one island.
Vocabulary before code
- Cell: one square of the grid, named by its row and column.
- Neighbour: a cell directly up, down, left or right of another cell.
- Island: a group of land cells that can reach each other through neighbours.
- Set: in union-find, a group of items that are known to be connected. Every item belongs to exactly one set.
- Representative: one item chosen to stand for its whole set. Two items are in the same set when they have the same representative. The representative is also called the root.
- find: the operation that returns the representative of an item's set.
- unite: the operation that joins two sets into one. It is also called union or merge.
- Flat index: a single number for a cell, so that every cell has a slot in one list. For a grid with
colscolumns, the flat index of(r, c)isr * cols + c.
Why not recount after every step
Here is the simplest method. After each new land cell, run flood fill from every land cell that has not been visited yet, and count how many times you had to start a new flood fill. Each count looks at every cell in the grid. For a grid with R rows and C columns, one count costs about R times C steps.
If the list has K positions, the total cost is about K times R times C steps. For a grid of 1000 by 1000 cells with 10000 positions, that is about 10000 times 1000000, which is 10 billion steps. That is too slow for a single program run.
Union-find avoids recounting the whole grid. Each new land cell does a small, fixed amount of work. It looks at up to four neighbours and joins at most four groups. The work per position is close to a constant, so the total cost is close to K steps plus the cost of setting up the grid, which is R times C.
The key idea: each new cell adds one, each merge takes one away
Start with a count of zero islands. When a new land cell arrives, it begins as its own island, so the count goes up by one.
Then look at the four neighbours of the new cell. For each neighbour that is land, the new cell touches it. Ask union-find whether the neighbour is already in the same island as the new cell.
- If it is not, the two islands join into one. Two islands became one, so the count goes down by one.
- If it is, nothing changes. The two cells were already connected through another path.
The unite call answers exactly this question. It returns true when two different sets were joined, and false when they were already one set. The code subtracts one only when it gets true.
Here is the 3 by 3 example worked by hand.
| Step | Cell added | Land neighbours | Islands now |
|---|---|---|---|
| 1 | (0,0) | none | 1 |
| 2 | (0,1) | (0,0) | 1 |
| 3 | (1,2) | none | 2 |
| 4 | (2,1) | none | 3 |
At step 2, the new cell at (0,1) makes the count go up to 2 and then down by 1, because it joins the island at (0,0). So the count is 1 + 1 - 1, which is 1. The rest of the steps add a cell with no land neighbours, so each one adds 1.
Notice that we never need to know the shape of an island. We only need to know which islands are the same, and union-find keeps that answer up to date.
Flat numbers for cells
Union-find stores one entry per item, and it counts items from 0. So every cell needs a number from 0 to R times C minus 1. We use the flat index from the vocabulary section:
3 by 3 grid, flat index = row * 3 + col
0 1 2 (0,0)=0 (0,1)=1 (0,2)=2
3 4 5 (1,0)=3 (1,1)=4 (1,2)=5
6 7 8 (2,0)=6 (2,1)=7 (2,2)=8The cell (1, 2) has flat index 1 * 3 + 2, which is 5. The cell (2, 1) has flat index 2 * 3 + 1, which is 7.
Flat indices let us use a plain std::vector instead of a two-dimensional structure. A vector is the standard C++ resizable array. Element 5 of the vector is the slot for cell (1, 2).
The disjoint set class
This class holds the union-find data. Read it once for the shape. The details of its two speed tricks belong to the lesson on union-find deeper, so here we use them without re-deriving them.
class DisjointSet {
public:
explicit DisjointSet(int n) : parent_(n), size_(n, 1) {
for (int i = 0; i < n; ++i) parent_[i] = i;
}
int find(int x) {
while (parent_[x] != x) {
parent_[x] = parent_[parent_[x]];
x = parent_[x];
}
return x;
}
// Returns true when two different sets were merged.
bool unite(int a, int b) {
int ra = find(a);
int rb = find(b);
if (ra == rb) return false;
if (size_[ra] < size_[rb]) std::swap(ra, rb);
parent_[rb] = ra;
size_[ra] += size_[rb];
return true;
}
private:
std::vector<int> parent_;
std::vector<int> size_;
};Here is what each part does, in plain words.
parent_[x]holds the item thatxpoints to. At the start every item points to itself, so every item is its own representative.findfollows the pointers until it reaches an item that points to itself. That item is the representative. The loop also makes the path shorter as it goes, which keeps later calls quick.unitefinds the representative of each item. If both are the same, the items are already together, so it returnsfalse. Otherwise it points the smaller set's representative at the larger one's. Thesize_list keeps the size of each set so that the choice is quick.
The class needs #include <utility> for std::swap and #include <vector> for std::vector. A complete program with includes is shown below.
The full program
The function below takes the grid size and the list of positions. It returns the island count after each position. The is_land list records which cells are already land, so we can spot a position that was seen before.
#include <array>
#include <iostream>
#include <utility>
#include <vector>
// Paste the DisjointSet class from the section above here.
// The program does not compile without it.
std::vector<int> islandCounts(int rows, int cols,
const std::vector<std::pair<int, int>>& positions) {
constexpr std::array<int, 4> kDr{-1, 1, 0, 0};
constexpr std::array<int, 4> kDc{0, 0, -1, 1};
DisjointSet dsu(rows * cols);
std::vector<char> is_land(rows * cols, 0);
std::vector<int> answer;
int islands = 0;
for (auto [r, c] : positions) {
int id = r * cols + c;
if (is_land[id]) {
answer.push_back(islands);
continue;
}
is_land[id] = 1;
++islands;
for (int k = 0; k < 4; ++k) {
int nr = r + kDr[k];
int nc = c + kDc[k];
if (nr < 0 || nr >= rows || nc < 0 || nc >= cols) continue;
int nid = nr * cols + nc;
if (!is_land[nid]) continue;
if (dsu.unite(id, nid)) --islands;
}
answer.push_back(islands);
}
return answer;
}
void print(const std::vector<int>& v) {
for (int x : v) std::cout << x << ' ';
std::cout << '\n';
}
int main() {
print(islandCounts(3, 3, {{0, 0}, {0, 1}, {1, 2}, {2, 1}}));
print(islandCounts(3, 3, {{0, 0}, {0, 0}, {1, 0}, {0, 2}, {1, 1}}));
print(islandCounts(1, 5, {{0, 0}, {0, 4}, {0, 2}, {0, 1}, {0, 3}}));
}The two arrays kDr and kDc are the four neighbour offsets. The first pair, -1, 0, means one row up. The second pair, 1, 0, means one row down. The arrays kDc do the same for columns. Using std::array keeps the size of the list known to the compiler.
The bounds check on the next line stops the code from looking outside the grid. A cell in row 0 has no neighbour above it, so nr would be -1, which is not a valid row.
Here is what the program prints when it is compiled with g++ -std=c++20 -Wall and run. The compiler gave no warnings.
1 1 2 3
1 1 1 2 2
1 2 3 2 1The first line is the grid from the walkthrough. The answer is 1 1 2 3, which matches the hand trace.
The second line has a position repeated. The cell (0, 0) appears twice. The second time, the code sees that the cell is already land, writes the current count again, and moves on. The count stays at 1 after the repeat.
The third line adds five cells in the row, in the order 0, 4, 2, 1, 3. Here is the trace.
- Step 1 adds
(0, 0). The count is 1. - Step 2 adds
(0, 4). It has no land neighbours, so the count is 2. - Step 3 adds
(0, 2). Its neighbours(0, 1)and(0, 3)are water. The count is 3. - Step 4 adds
(0, 1). It touches(0, 0)and(0, 2). Those two islands are different, so the count goes3 + 1 - 2, which is 2. - Step 5 adds
(0, 3). It touches(0, 2), which is in the big island now, and(0, 4), which is alone. The count goes2 + 1 - 2, which is 1.
The last two steps show one new cell joining two islands at once. That is why the code checks every neighbour.
Two more examples of increasing difficulty
The next example is a 2 by 2 grid with the positions (0,0), (0,1), (1,0) and (1,1) in that order. It checks the case where a new cell touches two cells that are already in one island.
- After
(0,0)the count is 1. - After
(0,1)the new cell joins(0,0). The count stays at 1. - After
(1,0)the new cell joins(0,0). The count stays at 1. - After
(1,1)the new cell is added, so the count is 2. It touches(0,1)and merges, so the count is 1. It also touches(1,0). That cell is already in the same island, sounitereturnsfalse, and the count does not change.
The output is 1 1 1 1. The fourth cell closes a loop, which is why the second merge does nothing. If the code subtracted one for every land neighbour, it would print a number that is too small.
The last example has no merges at all. Consider a 3 by 3 grid with the positions (0,0), (0,2) and (1,1). The cells (0,0) and (0,2) are not neighbours. The cell (1,1) is diagonal to both of them, so it does not join either. The output is 1 2 3. Diagonal cells are not connected in this problem, and the code does not check them.
Common mistakes
Counting a repeated cell as a new island
If the is_land check is removed, a repeated position adds one to the count even though nothing changed on the map. With a 1 by 1 grid and the positions (0,0) and (0,0), the second position makes the count go up to 2, and the output becomes 1 2. The correct output is 1 1.
The fix is the early continue at the top of the loop. It handles a repeated position before any count changes.
Leaving out the bounds check
The bounds check stops a neighbour from being outside the grid. Without it, the flat index is computed from a column that is not on the grid, and the index can point at a cell in another row.
We tested this on a 2 by 3 grid with the positions (1, 0) and then (0, 2). We removed only the column check and kept the row check. The program printed:
1 1The correct output is 1 2, because the two cells do not touch. The cell (0, 2) has a right neighbour at column 3, which is off the grid. Its flat index is 0 * 3 + 3, which is 3. Flat index 3 is the cell (1, 0), which is land. So the code joined two cells that are not neighbours.
Ignoring the result of unite
If the code calls dsu.unite(id, nid) but does not subtract when the result is true, the count only goes up. The 3 by 3 example then prints 1 2 3 4 instead of 1 1 2 3. The union-find structure is correct, but the count is not updated from it.
Calling find with the wrong number of arguments
find needs the cell's flat index. Calling it with no argument is a compile error. We wrote a small program with int root = dsu.find(); and compiled it with g++ -std=c++20 -Wall. The compiler stopped with this message:
islands2_bad_call.cpp: In function ‘int main()’:
islands2_bad_call.cpp:14:24: error: no matching function for call to ‘DisjointSet::find()’
14 | int root = dsu.find();
| ~~~~~~~~^~
islands2_bad_call.cpp:14:24: note: there is 1 candidate
islands2_bad_call.cpp:6:9: note: candidate 1: ‘int DisjointSet::find(int)’
6 | int find(int x) { return parent_[x]; }
| ^~~~
islands2_bad_call.cpp:6:9: note: candidate expects 1 argument, 0 providedThe message says the function takes one argument and the call gave none. Pass the flat index of the cell.
Mixing up rows and columns in the flat index
The flat index is row * cols + col. On a 2 by 3 grid, the cell (0, 2) should have index 2. The swapped formula col * rows + row gives 2 * 2 + 0, which is 4. That is the index of the cell (1, 1). Keep rows and columns in the same order everywhere.
Practice
Each exercise asks for the output of islandCounts for a grid and a list of positions. Work out the answer on paper, then check it against the answer below it.
-
Grid 2 rows by 2 columns, positions
(0,0),(1,1),(0,1),(1,0).Show the answer
The output is
1 2 1 1. After(1,1)the count is 2, because the cell is diagonal to(0,0). After(0,1)it touches both, so the count goes2 + 1 - 2, which is 1. After(1,0)the count goes1 + 1 - 1, which is 1, because it touches(0,0)in another island. -
Grid 1 row by 3 columns, positions
(0,1),(0,0),(0,2).Show the answer
The output is
1 1 1. Each new cell touches the island that is already there, so the count goes up by one and then down by one each time. -
Grid 1 row by 1 column, positions
(0,0)and(0,0).Show the answer
The output is
1 1. The second position is a repeat, so the count stays the same. -
Grid 3 rows by 3 columns, positions
(0,0),(0,2)and(1,1).Show the answer
The output is
1 2 3. None of the three cells is a neighbour of another. -
Grid 2 rows by 2 columns, positions
(0,0),(0,1),(1,0)and(1,1).Show the answer
The output is
1 1 1 1. The last cell touches two islands that were already joined through the first three cells. The first merge returnstrueand subtracts one. The second merge returnsfalse, so nothing changes.
Summary
- Each new land cell starts as its own island, so the count goes up by one.
- Each neighbour that joins a different island takes the count down by one.
unitereturnstrueonly for a real merge, and the count changes only then.- A flat index
row * cols + collets a single vector hold the union-find data for the whole grid. - A repeated position must be detected and skipped, or the count goes up for a cell that did not change.