Hiểu bài toán

Bài toán yêu cầu tìm 'bao đóng' của đồ thị G=(V,E). Bao đóng G'=(E,V') của G được định nghĩa dựa trên tính chất đường đi: giữa hai đỉnh u và v trong G' có cạnh nối nếu và chỉ nếu có đường đi từ u đến v trong đồ thị gốc G.

Điều này có nghĩa: với mỗi cặp đỉnh (i, j) trong đồ thị gốc, ta cần kiểm tra xem có tồn tại một chuỗi các đỉnh (i, k1, k2, ..., km, j) sao cho mỗi cặp liên tiếp đều là cạnh trong G hay không. Nếu có, ta đặt A'[i][j] = 1 (và A'[j][i] = 1 vì đồ thị không có hướng), ngược lại đặt 0.

Tóm lại, bài toán yêu cầu tính ma trận kề của đồ thị có liên thông mạnh (Strongly Connected Components - SCC) hoặc chính xác hơn là ma trận của đồ thị mới thể hiện tính 'đường đi' giữa các đỉnh.

Các cách tiếp cận

Cách Thuật toán Floyd-Warshall

#include <bits/stdc++.h>

using namespace std;

int n;
int b[1002][1002];

int main()
{
    cin >> n;
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= n; j++)
            cin >> b[i][j];

    // Thuật toán Floyd-Warshall để tìm đường đi qua mọi đỉnh trung gian
    for(int k = 1; k <= n; k++)
    {
        for(int i = 1; i <= n; i++)
        {
            for(int j = 1; j <= n; j++)
            {
                if(i == j)
                {
                    b[i][j] = 0; // Đặt đường chéo về 0 (không có khuyên)
                    continue;
                }
                // Nếu có đường i -> k và k -> j thì có đường i -> j
                if(b[i][k] == 1 && b[k][j] == 1)
                    b[i][j] = 1;
            }
        }
    }

    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= n; j++)
            cout << b[i][j] << ' ';
        cout << endl;
    }
}

• Time Complexity: O(n^3)
• Space Complexity: O(n^2)

Đây là cách tiếp cận trực tiếp và dễ hiểu nhất dựa trên định nghĩa về đường đi. Ta sử dụng biến trung gian k để 'thử' tất cả các đỉnh có thể dùng làm cầu nối.

Logic:

• Khởi tạo ma trận kề B từ input.
• Với mỗi đỉnh k (từ 1 đến n), ta cập nhật ma trận: Nếu có đường từ i -> k và từ k -> j, thì chắc chắn có đường từ i -> j.
• Ta lặp lại quá trình này cho đến khi k chạy hết các đỉnh. Sau khi hoàn thành, B[i][j] = 1 khi và chỉ khi có đường đi từ i đến j.
• Trong code, vòng lặp if(i == j) b[i][j] = 0; dùng để đảm bảo không có cạnh khuyên (self-loop), nhưng theo logic bài toán, nếu i=j thì không cần quan tâm, kết quả thường yêu cầu ma trận kề của đồ thị mới không có khuyên.

Với n <= 1000, O(n^3) có thể là ~10^9 thao tác, khá sát thời gian giới hạn. Tuy nhiên, với C++ và optimization, nó có thể qua được.

Cách Duyệt DFS cho từng đỉnh (Tìm SCC)

#include <bits/stdc++.h>

using namespace std;

const int INF = 1000;

vector<int> a[INF];
vector<vector<int>> dp;
vector<int> vt(INF, 0);
int kq[INF][INF] = {0};

int c = 0;

// DFS để tìm các đỉnh thuộc cùng thành phần liên thông mạnh (từ u)
void dfs(int u) {
    vt[u] = 1;
    dp[c].push_back(u);
    for (int v : a[u]) {
        if (!vt[v]) {
            dfs(v);
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    unt n; cin >> n;
    dp.resize(n);

    // Xây dựng đồ thị
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            int x; cin >> x;
            if (x == 1) {
                a[i].push_back(j);
            }
        }
    }

    // Tìm các thành phần liên thông mạnh (hoặc nhóm liên thông nếu đồ thị vô hướng)
    for (int i = 0; i < n; ++i) {
        if (!vt[i]) {
            dfs(i);
            c += 1;
        }
    }

    // Xây dựng ma trận kề kết quả dựa trên các nhóm
    // Code gốc bị truncate, nhưng logic là:
    // Nếu 2 đỉnh nằm trong cùng 1 nhóm (dp[u]) thì đặt kq[u][v] = 1
    // Logic này đúng nếu bài toán là 'Bao đóng' (tìm tính chất đường đi)
    // Thực tế bài này cần DFS cả đồ thị ngược (hoặc dùng Tarjan) để tìm SCC.
    // Code mẫu chỉ minh họa ý tưởng DFS theo thành phần liên thông.

    return 0;
}

• Time Complexity: O(n^2)
• Space Complexity: O(n^2)

Cách này dựa trên nhận định: Hai đỉnh u và v có đường đi đến nhau nếu chúng nằm trong cùng một thành phần liên thông mạnh (SCC).

Quá trình:

1. Xây dựng đồ thị từ ma trận kề.
2. Sử dụng thuật toán Tarjan hoặc Kosaraju (hoặc đơn giản là DFS lan truyền) để tìm các SCC. Tuy nhiên, đoạn code trên chỉ đơn giản là duyệt DFS lan truyền từ các đỉnh chưa duyệt.
3. Sau khi xác định được các nhóm liên thông, ta đánh dấu tất cả các cặp đỉnh trong cùng một nhóm đều có nối với nhau (kq[u][v] = 1).

Đây là phương pháp tối ưu hơn Floyd-Warshall về mặt lý thuyết (O(n^2) thay vì O(n^3)), nhưng yêu cầu hiểu biết sâu hơn về cấu trúc đồ thị.

Cách Tối ưu Floyd-Warshall

#include <bits/stdc++.h>
using namespace std;

int n;
int a[1005][1005];

int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    cin >> n;
    for(int i = 0; i < n; ++i)
        for(int j = 0; j < n; ++j)
            cin >> a[i][j];

    for(int k = 0; k < n; ++k) {
        for(int i = 0; i < n; ++i) {
            if (a[i][k]) { // Tối ưu: Chỉ xét nếu có đường i -> k
                for(int j = 0; j < n; ++j) {
                    if (a[k][j]) a[i][j] = 1;
                }
            }
        }
    }

    for(int i = 0; i < n; ++i) {
        for(int j = 0; j < n; ++j)
            cout << a[i][j] << " ";
        cout << "\n";
    }
    return 0;
}

• Time Complexity: O(n^3) (thường nhanh hơn trong thực tế)
• Space Complexity: O(n^2)

Đây là biến thể của Floyd-Warshall được tối ưu hóa Bitset hoặc đơn giản là kiểm tra điều kiện trước khi lặp.

Logic:

• Thay vì lặp vô điều kiện for j, ta kiểm tra if (a[i][k]). Nếu không có đường từ i đến k, không cần thiết phải kiểm tra các điểm đến j thông qua k.
• Điều này giảm đáng kể số phép tính trong các đồ thị thưa (sparse).
• Với đồ thị đầy đủ (dense), độ phức tạp vẫn là O(n^3), nhưng với đồ thị thực tế, nó chạy nhanh hơn nhiều.

Đây là cách tiếp cận thực tiễn nhất cho n=1000 trong thời gian thi đấu nếu không muốn cài đặt DFS/Tarjan.

Phân tích độ phức tạp

Bài học kinh nghiệm

• Bài toán yêu cầu tìm tính chất 'có đường đi' giữa mọi cặp đỉnh. Ma trận kề của bao đóng chính là ma trận reachability (Reachability matrix).
• Thuật toán Floyd-Warshall là cách trực tiếp nhất để tính reachability matrix.
• Nếu coi mỗi thành phần liên thông mạnh (SCC) là một 'đỉnh' mới, bài toán quy về nối các SCC lại với nhau.

Lỗi thường gặp

• Quên xử lý trường hợp u = v (đường chéo ma trận). Thông thường ma trận kề của đồ thị mới không có khuyên.
• Sử dụng biến kiểu int cho các chỉ số mảng lớn (n=1000) có thể gây tràn số nếu tính toán thêm, nhưng với chỉ số mảng thì int thường đủ. Tuy nhiên, trong các phép nhân hoặc tính toán phức tạp hơn, long long nên được cân nhắc.
• Lỗi truy cập ngoài biên mảng nếu khai báo mảng với kích thước cố định (ví dụ 1000) nhưng input bắt đầu từ 1 hoặc n=1000 (chỉ số 999). Nên khai báo an toàn (1005).