Скачиваний:
30
Добавлен:
02.05.2014
Размер:
1.63 Кб
Скачать
#include "iostream.h"
#include "stdio.h"

bool existWay( int **array, int size, int from, int to ) {
	bool find = false;
	int i, j, k, step = 0;
	int **temp1, **temp2;
	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 ++ ){
			temp2[i][j] = array[i][j];	
		}
	}

	find = ( temp2[from][to] == 1 );
	while ( !find && step < size ){
		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];	
				}
			}
		}
		find = ( temp2[from][to] == 1 );
		step++;
	}

	return find;
}

void main() {
	int i, j;
	int from, to, size;
	int **array;
	bool answer;
    cout << "Exist Way.\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 << "Enter From Node: ";
	cin >> from;
	cout << "Enter To Node: ";
	cin >> to;
	answer = existWay( array, size, from - 1, to - 1 );
	cout << "\nExist way from " << from << " to " << to << " ?\nAnswer: " << ( answer ? "true" : "false" );
    cout << "\nPress \"Enter\" to continue..." << endl; 
    getchar();
}