Editorial for ptit010: Vương quốc ánh sáng

Hiểu bài toán

Xét một đồ thị vô hướng G gồm n đỉnh (thành phố) và các cạnh (cầu) được biểu diễn bởi ma trận kề. Ban đầu đồ thị có đúng 1 thành phần liên thông (bởi vì chỉ có 1 bang duy nhất). Nhiệm vụ là đếm số lượng cạnh cầu (cầu nối giữa 2 thành phố) mà nếu loại bỏ (đánh sập) sẽ làm tách đồ thị thành nhiều hơn 1 thành phần liên thông. Nói cách khác, ta cần đếm số cạnh cầu trong đồ thị.

Ma trận đầu vào: n dòng, mỗi dòng n số 0 hoặc 1. Tuy nhiên, theo quy tắc của các bài toán ma trận kề tại PTIT và mẫu ví dụ (ví dụ 2, đồ thị đầy đủ nhưng output là 0), ta chỉ xét các cạnh một lần (vô hướng) với điều kiện i < j.

• Input: 4 0 1 0 0 1 0 1 0 0 1 0 1 0 0 1 0
• Ma trận: Đồ thị đường thẳng 1-2-3-4. Các cạnh (1-2), (2-3), (3-4) đều là cầu. Output: 3.

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

Cách Brute Force (Loại bỏ từng cạnh và kiểm tra)

#include <stdio.h>
#include <string.h>

int n;
int graph[100][100];
int visited[100];
int removed_u, removed_v;

void dfs(int u) {
    visited[u] = 1;
    for (int v = 0; v < n; v++) {
        if (graph[u][v]) {
            // Bỏ qua cạnh đang xét (vô hướng)
            if ((u == removed_u && v == removed_v) || (u == removed_v && v == removed_u))
                continue;
            if (!visited[v])
                dfs(v);
        }
    }
}

int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            scanf("%d", &graph[i][j]);

    int count = 0;
    // Duyệt qua tất cả các cạnh (i, j) với i < j
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            if (graph[i][j]) {
                removed_u = i;
                removed_v = j;
                memset(visited, 0, sizeof(visited));

                // Thực hiện DFS từ đỉnh i
                dfs(i);

                // Nếu sau khi loại bỏ cạnh (i,j), đỉnh j không thể đến được từ i
                // => Cạnh này là cầu
                if (!visited[j]) {
                    count++;
                }
            }
        }
    }
    printf("%d", count);
    return 0;
}

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

Cách tiếp cận trực quan nhất là thử từng cạnh một.

1. Duyệt qua tất cả các cặp đỉnh (i, j) có nối nhau (i < j).
2. Với mỗi cạnh (i, j), ta 'tạm thời' loại bỏ nó ra khỏi đồ thị.
3. Thực hiện duyệt DFS/BFS từ đỉnh i để xem có thể đi đến bao nhiêu đỉnh.
4. Nếu đỉnh j không nằm trong tập hợp các đỉnh đi được từ i (tức visited[j] == 0), điều này có nghĩa là việc loại bỏ cạnh (i, j) đã làm đứt đường nối giữa i và j, làm đồ thị tách ra. Do đó (i, j) là một cạnh cầu.
5. Độ phức tạp: Với mỗi cạnh (tối đa ~n^2/2), ta làm một DFS (O(n^2) do ma trận kề)). Tổng cộng O(n^4) nếu duyệt ma trận đầy đủ, nhưng do chỉ xét i < j và ma trận kề nên thực tế là O(E * (V+E)) ~ O(n^2 * n^2) = O(n^4) nếu dùng danh sách kề O(V+E), nhưng với ma trận kề DFS là O(n^2). Tuy nhiên, với n <= 100, O(n^3) (n * n * (DFS on matrix n^2)) là chấp nhận được. Code mẫu tính O(n^3) do DFS qua ma trận.

Cách Tối ưu DFS (Đếm thành phần)

#include <stdio.h>
#include <string.h>

int n;
int adj[100][100];
int visited[100];
int removed_u, removed_v;

void dfs(int u) {
    visited[u] = 1;
    for (int v = 0; v < n; v++) {
        if (adj[u][v]) {
            if ((u == removed_u && v == removed_v) || (u == removed_v && v == removed_u))
                continue;
            if (!visited[v]) dfs(v);
        }
    }
}

int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            scanf("%d", &adj[i][j]);

    int ans = 0;
    for (int u = 0; u < n; u++) {
        for (int v = u + 1; v < n; v++) {
            if (adj[u][v]) {
                removed_u = u;
                removed_v = v;
                memset(visited, 0, sizeof(visited));

                int components = 0;
                // Đếm số thành phần liên thông sau khi loại bỏ cạnh
                for (int i = 0; i < n; i++) {
                    if (!visited[i]) {
                        dfs(i);
                        components++;
                    }
                }

                // Ban đầu là 1 thành phần. Nếu > 1 => tách thành phần
                if (components > 1) {
                    ans++;
                }
            }
        }
    }
    printf("%d", ans);
    return 0;
}

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

Cách này tương tự cách 1 nhưng logic kiểm tra khác: Thay vì chỉ xét đường đi từ u đến v, ta đếm tổng số thành phần liên thông của toàn đồ thị sau khi loại bỏ cạnh.

• Ban đầu đồ thị có 1 thành phần.
• Nếu loại bỏ cạnh (u, v) mà số thành phần liên thông tăng lên (> 1), tức là đồ thị bị tách.
• Cụ thể, ta duyệt qua tất cả các đỉnh chưa thăm và gọi DFS. Nếu chỉ cần 1 lần gọi DFS thăm hết toàn bộ đỉnh thì đồ thị vẫn liên thông (1 thành phần). Nếu cần 2 lần gọi DFS trở lên, tức đồ thị đã tách.
• Độ phức tạp vẫn là O(n^3) do lặp qua các cạnh và thực hiện DFS (O(n^2)) cho mỗi cạnh.

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

Bài học kinh nghiệm

• Đồ thị đầu vào chỉ có 1 thành phần liên thông duy nhất.
• Một cạnh (u, v) là cầu nếu không tồn tại đường vòng nối u và v (không đi qua cạnh đó). Trong ma trận kề, ta có thể kiểm tra điều này bằng cách loại bỏ cạnh đó và xem u và v còn nối với nhau không, hoặc xem toàn bộ đồ thị có bị tách làm đôi không.
• Vì đồ thị nhỏ (n <= 100), thuật toán O(n^3) hoặc O(n^4) đều chạy tốt. Tuy nhiên, cách tiếp cận loại bỏ từng cạnh và đếm thành phần liên thông là ổn định và dễ hiểu.

Lỗi thường gặp

• Xử lý sai ma trận kề: Ma trận input có thể chứa cả A[i][j] và A[j][i]. Cần đảm bảo mỗi cạnh chỉ được xử lý một lần (ví dụ chỉ xét i < j) để tránh đếm trùng.
• Quên kiểm tra cạnh (u, v) khi DFS: Khi thực hiện DFS để kiểm tra tính liên thông sau khi loại bỏ cạnh (u, v), code DFS phải bỏ qua cạnh này. Nếu không, ta vẫn xem nó tồn tại và kết quả sai (không nhận ra nó đã bị loại bỏ).
• Biến toàn cục vs local: Cần reset biến visited và biến removed_u/v đúng cách giữa các lần lặp.