warshall.txt

来自「图论常用算法的C语言程序,对于图论的一些应用有很大的指导作用!」· 文本 代码 · 共 35 行

#include <stdio.h>               //求传递矩阵
#define N 510

bool m[N][N]={0};

void warshall(int n)
{
 bool m2[N][N]={0};
 int i,j,k;
 for(k=1;k<=n;k++)
 {
  for(i=1;i<=n;i++) for(j=1;j<=n;j++) m2[i][j]=m[i][j];
  for(i=1;i<=n;i++) {for(j=1;j<=n;j++) {m[i][j]=m2[i][j]||(m2[i][k]&&m2[k][j]);}}
  for(i=1;i<=n;i++) 
  {
   for(j=1;j<=n;j++)
    printf("%d ",m[i][j]);
   printf("\n");
  }
  printf("\n");
 }
}

int main()
{
 int n,k,i,a,b;
 scanf("%d %d",&n,&k);
 for(i=1;i<=k;i++)
 {
  scanf("%d %d",&a,&b);
  m[a][b]=true;
 }
 warshall(n);
 scanf("%d",&i);
}