alg1.cpp

#include <stdio.h>
#include <conio.h>

using namespace std;

int n,k,i,j;
int a[100][100]; //матрица смежности исходного ориентированного графа

int main()
{
	freopen("input.txt","r",stdin); //перенаправляем ввод из файла на ввод с клавиатуры
	scanf("%d",&n); //прочитали количество вершин графа
	
	//прочитали матрицу смежности графа n x n
	for(i=0;i<n;i++) 
		for(j=0;j<n;j++) scanf("%d",&a[i][j]);
	
	//запускаем алгорит флойда-уоршелла
	for(k=0;k<n;k++)
		for(i=0;i<n;i++)
			for(j=0;j<n;j++)
				if(a[i][k]==1 && a[k][j]==1) a[i][j] = 1;
			
	//в результате работы алгоритма матрица смежности a превратилась в матрицу достижимости
	//теперь если в i-й строке, j-м столбце находится 1 значит вершина j достижима из вершини i , 0 - если не достижима
	//таким образом построено транзитивное замыкание графа			
	
	//выводим матрицу транзитивного замыкания
	for(i=0;i<n;i++) //n строк 
	{
		for(j=0;j<n;j++) printf("%d ",a[i][j]);  //в каждой n значений
		printf("\n");
	}
	getch();
	return 0;
}