Шпоры по МПиПА / Графы / Определение числа компонент связности / C / Исходник / ConnectionComponents

#include "iostream.h"
#include "stdio.h"

int numberConnectionComponents( int **array, int size ) {
	bool find = false;
	int i, j, k, step = 0;
	int **temp1, **temp2, **sum;
	int maxComponent = 0;
	int *components;
	bool allComponentsFind;

	sum = new int*[size];
	for ( i = 0; i < size; i ++ ){
		sum[i] = new int[size];
	}

	temp1 = new int*[size];
	for ( i = 0; i < size; i ++ ){
		temp1[i] = new int[size];
	}

	temp2 = new int*[size];
	for ( i = 0; i < size; i ++ ){
		temp2[i] = new int[size];
	}


	for ( i = 0; i < size; i ++ ){
		for ( j = 0; j < size; j ++ ){
			sum[i][j] = temp2[i][j] = 0;	
		}
	}
	for ( i = 0; i < size; i ++ ){
		sum[i][i] = temp2[i][i] = 1;
	}

	for ( step = 1; step <= size; step ++ ){
		for ( i = 0; i < size; i ++ ){
			for ( j = 0; j < size; j ++ ){
				temp1[i][j] = temp2[i][j];	
			}
		}
		for ( i = 0; i < size; i ++ ){
			for ( j = 0; j < size; j ++ ){
				temp2[i][j] = 0;
				for ( k = 0; k < size; k ++ ){
					temp2[i][j] += temp1[i][k]*array[k][j];	
				}
			}
		}
		for ( i = 0; i < size; i ++ ){
			for ( j = 0; j < size; j ++ ){
				sum[i][j] += temp2[i][j];	
			}
		}
	}

    maxComponent = 0;
	components = new int[size];
	for ( i = 0; i < size; i ++ ){
		components[i] = 0;
	}

	allComponentsFind = true;
    for ( i = 0; i < size; i ++ ){
		if ( components[i] == 0 ) {
            allComponentsFind = false;
            break;
		}
	}

    while ( !allComponentsFind ){
		for ( i = 0; i < size; i ++ ){
            if ( components[i] == 0 ){
				j = i;
				maxComponent++;
				components[i] = maxComponent;
				break;
			}
		}
        for ( i = j + 1; i < size; i ++ ){
			if ( ( sum[j][i] > 0 ) || ( sum[i][j] > 0 ) && ( components[i] == 0 ) ){
				components[i] = maxComponent;
            }
		}
		allComponentsFind = true;
		for ( i = 0; i < size; i ++ ){
			if ( components[i] == 0 ) {
				allComponentsFind = false;
				break;
			}
		}
    }

	return maxComponent;
}

void main() {
	int i, j;
	int size;
	int **array;
    cout << "Connection components.\nEnter graph dimension: ";
    cin >> size;
	array = new int*[size];
	for ( i = 0; i < size; i++ ) {
		array[i] = new int[size];
	}
	for ( i = 0; i < size; i ++ ){
		cout << "Enter " << i + 1 << " row: ";
		for ( j = 0; j < size; j ++ ){
			cin >> array[i][j];
		}
	}
	cout << "\nNumber of connection components: " << numberConnectionComponents( array, size );
    cout << "\nPress \"Enter\" to continue..." << endl; 
    getchar();
}