srand (time (NULL));
for (int i=0; i<n; i++)
     for (int j=0; j<n; j++)
         a[i][j] = rand () % 2;

#include <time.h>
#include <conio.h>
#include <iostream>		
#include <assert.h>
using namespace std;	




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; }


protected:
	int*	labels;
	int		m_nLabels;     // длина массива
};

// конструктор устанавливает структуры данных, необходимые находка объединение реализацией.
UnionFind::UnionFind( int max_labels )
{
	m_nLabels = max_labels;
	labels = new int[m_nLabels];
	labels[0] = 0;
}

// Деструктор освобождает память
UnionFind::~UnionFind()
{
	m_nLabels = 0;
	delete labels;
	labels = 0;
}


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;
}

int UnionFind::Union(int x, int y)
{
	return labels[find(x)] = find(y);
}

// make_set creates новый эквивалентный класс и возвращения его метка
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, double p );
	~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;
  double probability;
};


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

	//заполнение матрицы
	int c1 = nRows*nCols*p; //число единиц
	int k1 = 0;
	int ofs_r, ofs_c;
	srand (time(NULL));
	while (k1<c1) {
		ofs_r = rand()%nRows;
		ofs_c = rand()%nCols;
		if (matrix[ofs_r][ofs_c]!=0) continue;
		matrix[ofs_r][ofs_c] = 1;
		k1++;
	}
	//--------------------
}

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;
}


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". возвращает кол-во найденных кластеров.
int Matrix::hoshen_kopelman()
{
	UnionFind uf( m_nRows*m_nCols/2 );
	
	// просмотр матрицы 
	for( int i=0; i<m_nRows; i++ )
		for (int j=0; j<m_nCols; j++)
			if( matrix[i][j] ) {						// если занято...
				int up = (i==0 ? 0 : matrix[i-1][j]);   // смотрим вверх
				int left = (j==0 ? 0 : matrix[i][j-1]); // смотрим влево
				switch (!!up + !!left) {
				case 0:
					matrix[i][j] = uf.make_set();		// новый кластер
					break;
					
				case 1:									// часть существующего кластера
					matrix[i][j] = max(up,left);		// какой бы ни является отличным от нуля, помечен
					break;
					
				case 2:									// связываем 2 кластера
					matrix[i][j] = uf.Union(up, left);
					break;
				}
			}
			
	// примените перемаркирование к матрице

	
	int* new_labels = new int[uf.getNumLabels()]; // распределите массив, инициализированный, чтобы обнулить
	memset( new_labels, 0, sizeof(int)*uf.getNumLabels() );
	
	for(int 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;
}


// Эта процедура выясняет что любые занятые соседи 
//имеют ту же самую метку.
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 );
			}
}



int main()
{
 	int m, n;
	cout<<"Vvedite kol-vo strok and colon"<<endl;
	cin >> m >> n;	// m = строки, n = стобцы
	
	for (double p = 0.1; p<=1; p+=0.1) { //перебираем вероятности
		if (p>0.9) p=1;
		Matrix matrix( m, n, p );

		// вывод матрицы
		cout << " --input-- \n" << matrix; 

		// поиск кластеров
		int clusters = matrix.hoshen_kopelman();

		// вывод результатов
		cout << " --output-- \n" << matrix;

		matrix.check_labelling();

		cout << "HK reports " << clusters << " percolyaciya est' \n";
	}

	getch();
	return 0;
}

  1  0  1  0  0  1  0
  1  0  0  0  1  1  0
  1  1  1  0  1  1  1
  1  1  1  1  1  1  0
  0  1  1  0  0  1  1
  0  1  1  1  0  0  0
  0  0  1  0  1  1  1
 

  1  0  2  0  0  1  0
  1  0  0  0  1  1  0
  1  1  1  0  1  1  1
  1  1  1  1  1  1  0
  0  1  1  0  0  1  1
  0  1  1  1  0  0  0
  0  0  1  0  3  3  3

ПОРОГ ПЕРКОЛЯЦИИ 
Поскольку неудобно генерировать перколяционные конфигурации с по- 
мощью калькулятора, мы разработаем простую программу. Рассмотрим 
квадратную решетку со стороной L и присвоим каждой ячейкой этой ре- 
шетки случайные числа от нуля до единицы. Ячейка занимается, если 
присвоенное ей случайное число меньше р. Программа site, распечатка 
которой приведена ниже, порождает ячеечную перколяцнонную конфнгу- 
рацию и выводит ее на экран компьютера для наглядного представления 
кластеров, В массиве г основной программы хранятся случайные числа, 
присваиваемые каждой ячейке. Заметим, что каждой ячейке решетки 
присваивается случайное число, так что если р увеличивается, то за- 
нятые ячейки остаются занятыми. 
PROGRAM site	1 рисуются конфигурации ячеечной перколяции 
DIM rE0,50) 
RANDOMIZE 
CALL initial(L)	1 задаются параметры решетки и экрана 
CALL Mtice(L,r)	1 придание каждой ячейке случайного числа 
CALL configuration L, г)	I занятие ячеек с дайной вероятностью р 
END 
SUB initial (L) 
INPUT prompt "размер решетки = ": L 
LET aspect_ratio =1.5	I значение для компьютера Macintosh 
LET margin = 0.1*L 
LET mx = aspect_ratio*margin 
LET bx = aspect_ratio*L 
SET window -mx, bx + mx,-margin, L + margin 
BOX LINES O,L,O,L 
END SUB 
SUB lattice (L,r(,)) 
FOR row = 1 to L	I рисование ячеек решетки 
LET у = r°w - 0.5 
1 связывает с каждой ячейкой квадрат со стороной 1 
FOR col = 1 to L 
LET x = col - 0.5 
LET r( col, row) = rnd 1 каждой ячейке придается случайное число 
PLOT POINTS: x,y 
NEXT col 
NEXT row 
END SUB 
SUB configuration ( L, r(,)) 
DIM Ц50.50) 
DO while p >= 0 
SET cursor 1,1 
INPUT prompt "вероятность p = ": p 
LET size = 0.4	I половина стороны квадрата для занятых ячеек 
FOR row = 1 to L 
LET у = row - 0.5 
FOR col = 1 to L 
IF r( col, row) < p and s{ col, row) о 1 then I ячейку занимаем 
LET x = col - 0.5 
BOX AREA x - size.x + size, у - size, у + size 
LET s( col, row) = 1	I ячейка занята 
END IF 
NEXT col 
NEXT row 
LOOP 
END SUB 
Порог перколяцни pc определяется как такая вероятность р, прн 
которой появляется первый бесконечный кластер на бесконечной решет- 
ке. Однако для конечной решетки со стороной L. которую мы можем 
промоделировать на компьютере, всегда существует ненулевая вероят- 
ность того, что будет появляться соединяющий кластер, связывающий 
одну сторону решетки с другой. Для малых значений р эта вероятность 
порядка р (рис. 12.4). По мере увеличения L эта величина стремится 
к нулю, и для достаточно малых значений р будут существовать только 
конечные кластеры. Поскольку нам необходимо применить правило «про- 
текания» для конечной решетки, мы определим РСЩ как среднее зна- 
чение р, прн котором впервые появляется соединяющий кластер. Для 
конечной решетки определение протекания произвольно и, следователь- 
но, вычисленное значение рс зависит от критерия протекания. Напри- 
мер, мы можем определить соединяющий путь одним из способов: он 
связывает решетку либо в горизонтальном, либо в вертикальном на- 
правлении; соединяет решетку в выбранном направлении (например, в 
вертикальном); соединяет решетку в обоих направлениях. Все этн пра- 
вила протекания должны приводить к одному и тому же экстраполиро- 
ванному значению р при L —» оо. В следующей ниже задаче мы получим 
приближенное значение р с точностью около 10%. Более тонкий ана- 
лиз, который называется конечномерным масштабированием, позволит 
нам экстраполировать результаты рс на предельный случай L —> со. 
 

PROGRAM continuum 1 рисуются конфигурации непрерывной перколяции 
RANDOMIZE 
CALL initial(L)	1 см. распечатку подпрограммы в программе site 
CALL disks(L)	I случайное размещение дисков в квадрате 
END 
SUB di$k${L) 
LET г = 0.5	I радиус дисков 
LET area = L*L	I L - сторона квадрата 
DO while n >= 0 
SET cursor 5,48 
INPUT prompt "число новых дисков = ": n 
FOR i = 1 to n 
LET x = rnd*L 1 центр диска внутри квадрата 
LET у = rnd*L 
BOX CIRCLE x - r, x + г, у - r- Y + r 
NEXT i 
LET number = number + n 
SET cursor 1,1 
PRINT "	";	! стирание строки 
SET cursor 1,1 
PRINT "плотность дисков = "; number/area; 
LOOP 
END SUB 
При обсуждении перколяции мы подчеркнули, что существует порог 
перколяции рс и появляется соединяющий путь, или кластер, прн р г 
s рс. Более полную информацию можно получить из распределения сред- 
него размера кластеров п (р), определяемого формулой 
п(р) =(среднее число кластеров размером s)/( полное число ячеек решетки 
).
При р >= рс соединяющий кластер исключается из ns. (По историческим 
причинам под размером кластера подразумевается число ячеек в клас- 
тере, а ие его пространственная протяженность.) Тщательное изучение 
 показывает, что  ns(p = 0) = 5/64, 1/64 и 2/64 для s = 
= 1, 2 и 3 соответственно и равно нулю в противном случае. Посколь- 
ку сумма(Sns) представляет собой полное число занятых ячеек, a Sns~ко- 
личество занятых ячеек в кластере размером s, величина 
sn является вероятностью того, что занятый узел, выбранный случайным 
образом, принадлежит кластеру размером s. 
В качестве примера рассмотрим рис. 12.3,а. Средний размер кластера, 
соответствующий восьми кластерам на этом рисунке, равен 5 = 27/13. 
Другой величиной, характеризующей перколяцию, является Рбеск(р) — 
вероятность того, что занятая ячейка принадлежит соединяющему клас- 
теру. Функция Рбеск(р) определяется следующим образом: 
Рбеск=(число ячеек в соединяющем кластере)/(полное число занятых ячеек).
В случае бесконечной решетки Рбеск(р) = 0 при р < р и Pбеск(p) = 1 при 
р = 1.