Initially you look for all the connected components of a single number, that is you look for all the different connected components of 1, 2, … and so on. You assign a unique identifier to each of these components, in the Author’s solution it is the variable ptr. Next, a particular cell in the original matrix, say m[i][j] is also assigned the identifier of the connected component it belongs to, the Author stores all this assignment in a matrix called ‘visited’. In simple words, if a particular cell m[i][j] belongs to a component with identifier = k, then visited[i][j] = k. Once we have a unique identifier for every component we can save their sizes as well as their parent, this what happens in code snippet
who[i] = i;
sz[i] = sizes[i];
ans = max(ans, sz[i]);
The above code is the basic implementation of DSU, where initially every node is made parent of itself(I hope you understand DSU well before attempting this question).
Now let us answer your questions:
// But, how are we finding if the components are adjacent?
Look at this code snippet from the Author’s solution, it is where we find if two components are adjacent:
for (int x = 1; x <= n; ++x) {
for (int y = 1; y <= m; ++y) {
for (int k = 0; k < 4; ++k) {
int nx = x + dx[k], ny = y + dy[k];
if (a[nx][ny] <= a[x][y]) {
continue;
}
ed[make_pair(a[x][y], a[nx][ny])].push_back(make_pair(visited[x][y], visited[nx][ny]));
}
}
}
In case you did not understand the above part, we are essentially traversing every cell in the original
matrix, then for the current cell m[i][j] we are checking if a different number exist in cells adjacent to it, this what the loop for (int k = 0; k < 4; ++k) does, it checks all the four(top, right, bottom, left) cells for finding if the number is different, author has used the equality check if (a[nx][ny] <= a[x][y]) continue instead of if(a[nx][ny] == a[x][y]) continue just to avoid redundant calculations(if you already checked all the combinations of 1 and 3, you don’t need to check all combinations of 3 and 1). Next, if the number is different we say them in a map, the key is pair representing the number themselves(that is, say, 1 and 3) and value is also a pair which is their unique identifier(visited[i][j] remember?), which we will later use for joining Disjoint Components(the DSU implementation!).
// Also, how are we managing the situation where we need to merge an already connected component to the next component?
This is take cared by the DSU implementation, two components/sets are already connected if they have the same root(read about DSU first if you don’t understand what I mean), root can be obtained by recursively moving to the parent node of the current node, unless the current node is parent of itself(root is parent of itself), parents are stored in the who array.
This what basically done, in the part:
for (auto &vec : ed) {
vector < int > changed;
for (auto &it : vec.second) {
int x = it.first, y = it.second;
changed.push_back(x);
changed.push_back(y);
int xx = getWho(x), yy = getWho(y);
if (xx == yy) {
continue;
}
if (rand() & 1) {
swap(xx, yy);
}
who[xx] = yy;
sz[yy] += sz[xx];
ans = max(ans, sz[yy]);
}
for (auto &it : changed) {
sz[it] = sizes[it];
who[it] = it;
}
}
You each pair stored in your map and join the components if they are not already joined and save their sizes. The last part
for (auto &it : changed) {
sz[it] = sizes[it];
who[it] = it;
}
is part for restoring any changes made (because it is not necessary that a component 3 will be connected with 1, so restore any changes made above).
Hope it helps.