Chương trình tìm số nhóm tháp truyền thông tối thiểu trong C++

Giới thiệu

Cho ma trận nhị phân 2D, 1 là tháp truyền thông, 0 là ô trống. Hai tháp giao tiếp được nếu cùng hàng hoặc cùng cột. Tính chất bắc cầu: A nói với B, B nói với C ⇒ A nói với C. Tìm số nhóm tháp liên thông.

Ví dụ

Ma trận: {{1,1,0}, {0,0,1}, {1,0,1}} → Kết quả: 1 (tất cả tháp cùng một nhóm).

Ý tưởng giải thuật (DFS)

1. Duyệt ma trận, khi gặp ô giá trị 1 (tháp chưa thăm), tăng bộ đếm nhóm và gọi DFS.
2. DFS(i, j): đánh dấu ô hiện tại = 2 (đã thăm). Duyệt toàn bộ hàng i và cột j:
   • Với mỗi hàng p khác i: nếu matrix[p][j] == 1 → DFS(p, j).
   • Với mỗi cột q khác j: nếu matrix[i][q] == 1 → DFS(i, q).
3. Trả về tổng số nhóm.

Lưu ý: Code gốc dùng modulo ((i+k)%n) gây duyệt vòng (wrap-around), không đúng với đề bài thông thường. Phiên bản dưới đây đã sửa.

Ví dụ triển khai (C++)

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

class Solution {
public:
    void dfs(vector<vector<int>>& matrix, int i, int j, int n, int m) {
        matrix[i][j] = 2; // đánh dấu đã thăm
        // Duyệt cùng cột
        for (int p = 0; p < n; p++) {
            if (matrix[p][j] == 1)
                dfs(matrix, p, j, n, m);
        }
        // Duyệt cùng hàng
        for (int q = 0; q < m; q++) {
            if (matrix[i][q] == 1)
                dfs(matrix, i, q, n, m);
        }
    }
    
    int countGroups(vector<vector<int>>& matrix) {
        int n = matrix.size(), m = matrix[0].size();
        int groups = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (matrix[i][j] == 1) {
                    groups++;
                    dfs(matrix, i, j, n, m);
                }
            }
        }
        return groups;
    }
};

int main() {
    Solution ob;
    vector<vector<int>> v = {{1,1,0}, {0,0,1}, {1,0,1}};
    cout << ob.countGroups(v); // 1
    return 0;
}

Đầu vào

{{1,1,0}, {0,0,1}, {1,0,1}}

Đầu ra

1