STANAANDREY

roy warshall cls

Feb 9th, 2021 (edited)
755
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.76 KB | None | 0 0
  1. #include <iostream>
  2. using namespace std;
  3. #define NMAX 103
  4. int n, m;
  5. bool a[NMAX][NMAX];
  6.  
  7. void read() {
  8.     cin >> n >> m;
  9.     for (int i = 0; i < m; i++) {
  10.         int x, y;
  11.         cin >> x >> y;
  12.         a[x][y] = true;
  13.     }
  14. }
  15.  
  16. void RoyWarshall() {
  17.     for (int k = 1; k <= n; k++) {
  18.         for (int i = 1; i <= n; i++) {
  19.             for (int j = 1; j <= n; j++) {
  20.                 if (!a[i][j]) {
  21.                     a[i][j] = a[i][k] && a[k][j];
  22.                 }
  23.             }
  24.         }
  25.     }
  26. }
  27.  
  28. void write() {
  29.     for (int i = 1; i <= n; i++) {
  30.         for (int j = 1; j <= n; j++) {
  31.             cout << a[i][j] << ' ';
  32.         }
  33.         cout << endl;
  34.     }
  35. }
  36.  
  37. int main() {
  38.     read();
  39.     RoyWarshall();
  40.     write();
  41.     return 0;
  42. }
Add Comment
Please, Sign In to add comment