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

Exemplu

Intrare

6 9
1 2
1 3
1 5
3 5
4 1
3 4
5 1
6 1
6 3

Ieșire

1 1 1 1 1 0 
0 0 0 0 0 0 
1 1 1 1 1 0 
1 1 1 1 1 0 
1 1 1 1 1 0 
1 1 1 1 1 0

#include <bits/stdc++.h>

using namespace std;

int n , m , a[101][101];

void Warshall()
{
    for (int k = 1; k <= n; ++k)
        for (int i = 1; i <= n; ++i)
            for (int j = 1; j <= n; ++j)
                if (!a[i][j])
                    a[i][j] = a[i][k] && a[k][j];
}

int main()
{
    cin >> n >> m;
    int x, y;
    for(int i = 1 ; i <= m ; i++)
    {
        cin >> x >> y;
        a[x][y] = 1;
    }

    Warshall();
    for (int x = 1; x <= n; ++x)
    {
        for (int y = 1; y <= n; ++y)
            cout << a[x][y] << ' ';
        cout << '\n';
    }
}