Xây dựng bao bao hàm (Transitive Closure) bằng thuật toán Warshall trong C++

Cho đồ thị có hướng, ma trận bao bao hàm (transitive closure) cho biết đỉnh j có đạt được từ đỉnh i không (có đường đi). Thuật toán Warshall (Floyd-Warshall biến thể) tính ma trận này bằng quy hoạch động.

Thuật toán

Bắt đầu
  Nhập số đỉnh n
  Khởi tạo ma trận kề adj[n][n] (1 nếu có cạnh, 0 nếu không)
  Với k = 0..n-1:
    Với i = 0..n-1:
      Với j = 0..n-1:
        adj[i][j] = adj[i][j] || (adj[i][k] && adj[k][j])
  In ma trận adj
Kết thúc

Ví dụ minh họa

#include <iostream>
using namespace std;

int main() {
    int n; cout << "So dinh: "; cin >> n;
    int adj[20][20] = {0};
    char ans;
    for (int i=0; i " << char('a'+j) << "? (y/n): ";
            cin >> ans; adj[i][j] = (ans=='y');
        }

    // Warshall
    for (int k=0; k

Kết quả (ví dụ)
So dinh: 4
Co canh a -> a? y
Co canh a -> b? y
Co canh a -> c? n
Co canh a -> d? n
Co canh b -> a? y
Co canh b -> b? n
Co canh b -> c? y
Co canh b -> d? n
Co canh c -> a? y
Co canh c -> b? n
Co canh c -> c? n
Co canh c -> d? n
Co canh d -> a? y
Co canh d -> b? n
Co canh d -> c? y
Co canh d -> d? n

Transitive Closure:
   a b c d
a  1 1 0 0
b  1 0 1 0
c  1 0 0 0
d  1 0 1 0