C++でUnion-Find（素集合データ構造）を使って島の数を数える方法

問題の概要

この問題では、2次元のバイナリ行列（0と1だけで構成されたマトリックス）が与えられます。私たちのタスクは、素集合データ構造（Union-Find）を使って島の数を求めることです。

ここでいう「島」とは、行列の中で縦・横・斜めのいずれかの方向に隣接している1つ以上の「1」から構成される領域のことを指します。

具体例で理解する

入力：

bin[][] = {{ 1 0 0 0}
   {0 1 0 1}
   {0 0 0 0}
   {0 0 1 0}}

出力：

3

解説：

島は以下の3つ：
   bin00 - bin11
   bin13
   bin32

解法のアプローチ

この問題は、素集合データ構造（Disjoint Set Union、通称Union-Find）を用いることで効率的に解くことができます。大まかな流れは以下の通りです。

1. 行列全体を走査し、各セルについて8方向（上下左右＋斜め4方向）の隣接セルを確認します。
2. 隣接セルの値が「1」であれば、現在のインデックスとその隣接セルを Union（結合）します。
3. 続いて2回目の走査を行い、値が「1」のセルごとに find を呼び出して、属する集合のルート（代表元）を特定します。
4. そのルートがまだ出現していなければ、島のカウントを1つ増やします。

この手法により、隣接するすべての「1」が同じ集合へと統合され、最終的な異なるルートの数がそのまま島の数になります。

サンプルプログラム

以下は、上記の解法の動作を示すC++プログラムです。

#include <bits/stdc++.h>
using namespace std;
class DisjointUnionSets{
   vector<int> rank, parent;
   int n;
   public:
   DisjointUnionSets(int n){
      rank.resize(n);
      parent.resize(n);
      this->n = n;
      makeSet();
   }
   void makeSet(){
      for (int i = 0; i < n; i++)
      parent[i] = i;
   }
   int find(int x){
      if (parent[x] != x){
         return find(parent[x]);
      }
      return x;
   }
   void Union(int x, int y){
      int xRoot = find(x);
      int yRoot = find(y);
      if (xRoot == yRoot)
         return;
      if (rank[xRoot] < rank[yRoot])
         parent[xRoot] = yRoot;
      else if (rank[yRoot] < rank[xRoot])
         parent[yRoot] = xRoot;
      else {
         parent[yRoot] = xRoot;
         rank[xRoot] = rank[xRoot] + 1;
      }
   }
};
int findIslandCount(vector<vector<int>> mat){
   int n = mat.size();
   int m = mat[0].size();
   DisjointUnionSets *dus = new DisjointUnionSets(n * m);
   for (int j = 0; j < n; j++){
      for (int k = 0; k < m; k++){
         if (mat[j][k] == 0)
            continue;
         if (j + 1 < n && mat[j + 1][k] == 1)
            dus->Union(j * (m) + k, (j + 1) * (m) + k);
         if (j - 1 >= 0 && mat[j - 1][k] == 1)
            dus->Union(j * (m) + k, (j - 1) * (m) + k);
         if (k + 1 < m && mat[j][k + 1] == 1)
            dus->Union(j * (m) + k, (j) * (m) + k + 1);
         if (k - 1 >= 0 && mat[j][k - 1] == 1)
            dus->Union(j * (m) + k, (j) * (m) + k - 1);
         if (j + 1 < n && k + 1 < m && mat[j + 1][k + 1] == 1)
            dus->Union(j * (m) + k, (j + 1) * (m) + k + 1);
         if (j + 1 < n && k - 1 >= 0 && mat[j + 1][k - 1] == 1)
            dus->Union(j * m + k, (j + 1) * (m) + k - 1);
         if (j - 1 >= 0 && k + 1 < m && mat[j - 1][k + 1] == 1)
            dus->Union(j * m + k, (j - 1) * m + k + 1);
         if (j - 1 >= 0 && k - 1 >= 0 && mat[j - 1][k - 1] == 1)
            dus->Union(j * m + k, (j - 1) * m + k - 1);
      }
   }
   int *c = new int[n * m];
   int islands = 0;
   for (int j = 0; j < n; j++){
      for (int k = 0; k < m; k++){
         if (mat[j][k] == 1){
            int x = dus->find(j * m + k);
            if (c[x] == 0){
               islands++;
               c[x]++;
            }
            else
            c[x]++;
         }
      }
   }
   return islands;
}
int main(void){
   vector<vector<int>> 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}
   };
   cout<<"The number of islands in binary matrix is : "<<findIslandCount(mat);
}

出力結果

The number of islands in binary matrix is : 4

計算量について

このアルゴリズムは、ランクによる併合（Union by Rank）を用いているため、時間計算量はほぼ線形の O(n × m × α(n×m)) となります。ここで α はアッカーマン関数の逆関数であり、実用上は定数として扱えます。また、親配列とランク配列を保持するため、空間計算量は O(n × m) です。