Đếm số đảo nhị phân bằng Disjoint Set (Union-Find) C++

Mô tả bài toán

Cho ma trận nhị phân 2D. Đảo là nhóm các ô 1 liên thông (8 hướng). Đếm số đảo.

Ví dụ

mat = {{1,1,0,1,0},{0,1,0,1,1},{1,0,0,1,1},{0,0,0,0,0},{1,1,1,0,1}} → Output: 4.

Giải thuật (Disjoint Set Union)

1. Khởi tạo DSU cho n×m ô.
2. Duyệt ma trận: nếu ô = 1, union với 8 hàng xóm cũng = 1.
3. Duyệt lại: nếu ô = 1, find root. Nếu root chưa đếm → tăng số đảo.

Mã nguồn C++

#include <bits/stdc++.h>
using namespace std;

class DSU {
    vector<int> parent, rank;
public:
    DSU(int n): parent(n), rank(n,0) { iota(parent.begin(), parent.end(), 0); }
    int find(int x) { return parent[x]==x ? x : parent[x]=find(parent[x]); }
    void unite(int x, int y) {
        x=find(x); y=find(y);
        if (x==y) return;
        if (rank[x]=0 && nr=0 && nc seen(n*m,0);
    int islands=0;
    for (int r=0; r

The number of islands in binary matrix is : 4