Question

Cerința

Se dă lista arcelor unui graf orientat. Construiți matricea drumurilor, folosind algoritmul lui Roy-Warshall.
Date de intrare

Programul citește de la tastatură numărul n de noduri și numărul m de arce, iar apoi lista arcelor, formată din m perechi de forma i j, cu semnificația că există arc orientat de la i la j.
Date de ieșire

Programul va afișa pe ecran matricea drumurilor, câte o linie a matricei pe o linie a ecranului, elementele aceleiași linii fiind separate prin exact un spațiu.
Restricții și precizări

1 ≤ n ≤ 100

Answer 1

Răspuns:

#include<fstream>

#include<iostream>

using namespace std;

int k,m,n,x[105],a[105][105],p[105];

void citire()

{

   int x,y;

   cin>>n>>m;

   for(int i=1;i<=m;i++)

  {

      cin>>x>>y;

      a[x][y]=1;

  }

}

void rw()

{

   int i, j, k;

   for(k=1;k<=n;k++)

    for(i=1;i<=n;i++)

     for(j=1;j<=n;j++)

       if(a[i][j]==0)

        a[i][j]=a[i][k]*a[k][j];

}

void afis()

{

   for(int i=1;i<=n;i++)

   {

       for(int j=1;j<=n;j++)

       cout<<a[i][j]<<" ";

   cout<<endl;

   }

}

int main()

{

   citire();

   rw();

   afis();

}

Explicație: