Здравствуйте, Yulesik.

Алгоритм Хошена-Копельмана используется для нахождения связанных кластеров двумерной решетки. Каждая клетка решетки может быть пустой или заполненной. Клетки принадлежат одному кластеру, если они соприкасаются ребрами.

Алгоритм Х-К по сути является версией алгоритма объединение-поиск для двумерной решетки. Алгоритм объединение-поиск используется для объединения элементов множества в подмножества. Он содержит две процедуры: union(x, y), которая задает отношение эквивалентности двух элементов, т. е. определяет, что они принадлежат одному подмножеству и find(x), которая возвращает члена-представителя данного класса эквивалентности.

Реализация алгоритма:
1. Алгоритм Х-К для двумерной решетки. График количество кластеров - вероятность заполнения клетки. Реализация на C. http://www.ocf.berkeley.edu/~fricke/projects/hoshenkopelman/hoshenkopelman.html
2. Распараллеливание алгоритма Х-К с использованием конечного автомата. - http://www.cs.utk.edu/~berry/parhk/index.html

В приложении приведен вариант реализации алгоритма на C++, основанный на (1). Программа протестирована в MSVC++ 6.0, должна компилироваться (возможно, с минимальными изменениями) и другими компиляторами C++.

Чтобы не вводить матрицу вручную, создайте файл, содержащий матрицу в требуемом формате (см. комментарии в теле программы) и воспользуйтесь
перенаправлением ввода:
178336.exe < file_with_matrix

Успехов!

Приложение:
/*
Реализация алгоритма Хошена-Копельмана для маркировки кластеров на С++.
Based on Tobin Fricke's implementation of the Hoshen-Kopelman algorithm for
cluster labeling:
http://www.ocf.berkeley.edu/~fricke/projects/hoshenkopelman/hk.c
Описание алгоритма (на английском):
http://www.ocf.berkeley.edu/~fricke/projects/hoshenkopelman/hoshenkopelman.html
*/
#include <conio.h>
#include <iostream> // заменить на iostream.h для Borland C++
#include <assert.h>
using namespace std; // удалить для Borland C++

// -------------------------------------------------------------------
// Implementation of Union-Find Algorithm

class UnionFind
{
public:
UnionFind( int max_labels );
~UnionFind();

int find( int x );
int Union( int x, int y );
int make_set();

int getNumLabels() const { return m_nLabels; }
/* The 'labels' array has the meaning that labels[x] is an alias for the label x; by
following this chain until x == labels[x], you can find the canonical name of an
equivalence class. The labels start at one; labels[0] is a special value indicating
the highest label already used. */

protected:
int* labels;
int m_nLabels; // length of the labels array
};

// the constructor sets up the data structures needed by the union-find implementation.
UnionFind::UnionFind( int max_labels )
{
m_nLabels = max_labels;
labels = new int[m_nLabels];
labels[0] = 0;
}

// The destructor frees the memory used by the union-find data structures
UnionFind::~UnionFind()
{
m_nLabels = 0;
delete labels;
labels = 0;
}

// find returns the canonical label for the equivalence class containing x
int UnionFind::find(int x)
{
int y = x;
while (labels[y] != y)
y = labels[y];

while (labels[x] != x) {
int z = labels[x];
labels[x] = y;
x = z;
}
return y;
}

// Union joins two equivalence classes and returns the canonical label of the resulting class.
int UnionFind::Union(int x, int y)
{
return labels[find(x)] = find(y);
}

// make_set creates a new equivalence class and returns its label
int UnionFind::make_set()
{
labels[0] ++;
assert(labels[0] < m_nLabels);
labels[labels[0]] = labels[0];
return labels[0];
}

// End Union-Find implementation
// -------------------------------------------------------------------


class Matrix
{
public:
Matrix( int nRows, int nCols );
~Matrix();

int hoshen_kopelman();
void check_labelling();

// Оператор ввода
friend istream& operator>>( istream& stream, Matrix& m );
// Оператор вывода
friend ostream& operator<<( ostream& stream, const Matrix& m );

protected:
int m_nRows, m_nCols;
int** matrix;
};


Matrix::Matrix( int nRows, int nCols ) :
m_nRows( nRows ), m_nCols( nCols )
{
matrix = (int **)calloc( nRows, sizeof(int*) );
for( int i=0; i < nRows; i++ )
matrix[i] = (int *)calloc( nCols, sizeof(int) );
}

Matrix::~Matrix()
{
for( int i=0; i < m_nRows; i++ )
free( matrix[i] );
free( matrix );
}

istream& operator>>( istream& stream, Matrix& m )
{
for( int i=0; i < m.m_nRows; i++ )
for( int j=0; j < m.m_nCols; j++ )
stream >> m.matrix[i][j];

return stream;
}

/* operator<< prints out a matrix that is set up in the "pointer to pointers" scheme
(aka, an array of arrays); this is incompatible with C's usual representation of 2D
arrays, but allows for 2D arrays with dimensions determined at run-time
*/
ostream& operator<<( ostream& stream, const Matrix& m )
{
for( int i=0; i < m.m_nRows; i++ ) {
for( int j=0; j < m.m_nCols; j++ ) {
stream.width(3);
stream << m.matrix[i][j];
}
stream << endl;
}
return stream;
}

#define max(a,b) (a>b?a:b)
#define min(a,b) (a>b?b:a)

// Label the clusters in "matrix". Return the total number of clusters found.
int Matrix::hoshen_kopelman()
{
UnionFind uf( m_nRows*m_nCols/2 );

/* scan the matrix */
for( int i=0; i<m_nRows; i++ )
for (int j=0; j<m_nCols; j++)
if( matrix[i][j] ) { // if occupied ...
int up = (i==0 ? 0 : matrix[i-1][j]); // look up
int left = (j==0 ? 0 : matrix[i][j-1]); // look left
switch (!!up + !!left) {
case 0:
matrix[i][j] = uf.make_set(); // a new cluster
break;

case 1: // part of an existing cluster
matrix[i][j] = max(up,left); // whichever is nonzero is labelled
break;

case 2: // this site binds two clusters
matrix[i][j] = uf.Union(up, left);
break;
}
}

/* apply the relabeling to the matrix */

/* This is a little bit sneaky.. we create a mapping from the canonical labels
determined by union/find into a new set of canonical labels, which are
guaranteed to be sequential. */

int* new_labels = new int[uf.getNumLabels()]; // allocate array, initialized to zero
memset( new_labels, 0, sizeof(int)*uf.getNumLabels() );

for( i=0; i < m_nRows; i++)
for (int j=0; j < m_nCols; j++)
if (matrix[i][j]) {
int x = uf.find(matrix[i][j]);
if (new_labels[x] == 0) {
new_labels[0]++;
new_labels[x] = new_labels[0];
}
matrix[i][j] = new_labels[x];
}

int total_clusters = new_labels[0];

delete new_labels;
return total_clusters;
}


// This procedure checks to see that any occupied neighbors of an occupied site
// have the same label.
void Matrix::check_labelling()
{
for( int i=0; i < m_nRows; i++ )
for( int j=0; j < m_nCols; j++ )
if (matrix[i][j]) {
int N = ( i==0 ? 0 : matrix[i-1][j] );
int S = ( i==m_nRows-1 ? 0 : matrix[i+1][j] );
int E = ( j==m_nCols-1 ? 0 : matrix[i][j+1] );
int W = ( j==0 ? 0 : matrix[i][j-1] );

assert( N==0 || matrix[i][j]==N );
assert( S==0 || matrix[i][j]==S );
assert( E==0 || matrix[i][j]==E );
assert( W==0 || matrix[i][j]==W );
}
}

/* The sample program reads in a matrix from standard input, runs the HK algorithm on
it, and prints out the results. The form of the input is two integers giving the
dimensions of the matrix, followed by the matrix elements (with data separated by
whitespace).

a sample input file is the following:

8 8
1 1 1 1 1 1 1 1
0 0 0 0 0 0 0 1
1 0 0 0 0 1 0 1
1 0 0 1 0 1 0 1
1 0 0 1 0 1 0 1
1 0 0 1 1 1 0 1
1 1 1 1 0 0 0 1
0 0 0 1 1 1 0 1

this sample input gives the following output:

--input--
1 1 1 1 1 1 1 1
0 0 0 0 0 0 0 1
1 0 0 0 0 1 0 1
1 0 0 1 0 1 0 1
1 0 0 1 0 1 0 1
1 0 0 1 1 1 0 1
1 1 1 1 0 0 0 1
0 0 0 1 1 1 0 1
--output--
1 1 1 1 1 1 1 1
0 0 0 0 0 0 0 1
2 0 0 0 0 2 0 1
2 0 0 2 0 2 0 1
2 0 0 2 0 2 0 1
2 0 0 2 2 2 0 1
2 2 2 2 0 0 0 1
0 0 0 2 2 2 0 1
HK reports 2 clusters found
*/

int main()
{
/* Read in the matrix from standard input
The whitespace-deliminated matrix input is preceeded
by the number of rows and number of columns */

int m, n;
cin >> m >> n; // m = rows, n = columns
Matrix matrix( m, n );
cin >> matrix;

// print out an initial matrix
cout << " --input-- \n" << matrix;

// Process the matrix
int clusters = matrix.hoshen_kopelman();

// Output the result
cout << " --output-- \n" << matrix;

matrix.check_labelling();

cout << "HK reports " << clusters << " clusters found\n";

getch();
return 0;
}