これはユニオンファインドで解決できます（ただし、他の回答に示されているように、DFSはおそらく少し簡単です）。
このデータ構造の背後にある基本的な考え方は、同じコンポーネント内の要素を繰り返しマージすることです。これは、各コンポーネントをツリーとして表すことによって行われます（ノードは、その逆ではなく、自身の親を追跡します）。ルートノードに移動することで、2つの要素が同じコンポーネントにあるかどうかを確認でき、ノードをマージできます。一方のルートをもう一方のルートの親にするだけです。
これを示す短いコードサンプル：
const int w = 5, h = 5;
int input[w][h] = {{1,0,0,0,1},
{1,1,0,1,1},
{0,1,0,0,1},
{1,1,1,1,0},
{0,0,0,1,0}};
int component[w*h];
void doUnion(int a, int b)
{
// get the root component of a and b, and set the one's parent to the other
while (component[a] != a)
a = component[a];
while (component[b] != b)
b = component[b];
component[b] = a;
}
void unionCoords(int x, int y, int x2, int y2)
{
if (y2 < h && x2 < w && input[x][y] && input[x2][y2])
doUnion(x*h + y, x2*h + y2);
}
int main()
{
for (int i = 0; i < w*h; i++)
component[i] = i;
for (int x = 0; x < w; x++)
for (int y = 0; y < h; y++)
{
unionCoords(x, y, x+1, y);
unionCoords(x, y, x, y+1);
}
// print the array
for (int x = 0; x < w; x++)
{
for (int y = 0; y < h; y++)
{
if (input[x][y] == 0)
{
cout << ' ';
continue;
}
int c = x*h + y;
while (component[c] != c) c = component[c];
cout << (char)('a'+c);
}
cout << "\n";
}
}
ライブデモ。
上記は、アルファベットの異なる文字を使用しているものの各グループを示しています。
p i
pp ii
p i
pppp
p
これを変更して、コンポーネントを個別に取得したり、各コンポーネントに対応する要素のリストを取得したりするのは簡単です。cout << (char)('a'+c);1つのアイデアは、上記をcomponentMap[c].add(Point(x,y))-に置き換えることですcomponentMap。map<int, list<Point>>このマップの各エントリは、コンポーネントに対応し、ポイントのリストを提供します。
ユニオンファインドの効率を改善するためのさまざまな最適化がありますが、上記は単なる基本的な実装です。