Chương trình C++ đếm số tập phân chia đồ thị tối đa thỏa mãn điều kiện cạnh

Cho ma trận kề đồ thị G. Phân chia đỉnh thành các tập V1..Vk không rỗng sao cho mọi cạnh nối 2 đỉnh thuộc 2 tập liền kề. Tìm k tối đa, hoặc -1 nếu không thể.

Ví dụ

Đồ thị 6 đỉnh (ma trận cho trước), đầu ra 4.

Giải thuật

Chạy BFS từ mỗi đỉnh gán mức dp. Nếu gặp cạnh nối 2 đỉnh cùng mức hoặc chênh >1 → impossible (-1). Nếu hợp lệ, k = max(dp) + 1 (số mức khác nhau). Lấy max trên mọi điểm bắt đầu BFS.

Mã C++

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

int solve(vector<vector<int>> matrix) {
    int dp[210];
    int n = matrix.size();
    int fl = 1, ans = 0;
    for (int i = 0; i < n && fl; i++) {
        memset(dp, -1, sizeof(dp));
        dp[i] = 0;
        queue<int> q; q.push(i);
        while (!q.empty()) {
            int x = q.front(); q.pop();
            for (int j = 0; j < n; j++) {
                if (matrix[x][j] == 1) {
                    if (dp[j] == -1) { dp[j] = dp[x] + 1; q.push(j); }
                    else if (abs(dp[j] - dp[x]) != 1) fl = 0;
                }
            }
        }
        for (int j = 0; j < n; j++) ans = max(ans, dp[j]);
    }
    return (fl == 0) ? -1 : ans + 1;
}

int main() {
    vector<vector<int>> matrix = { {0,1,0,1,1,0}, {1,0,1,0,0,1}, {0,1,0,1,0,0}, {1,0,1,0,0,0}, {1,0,0,0,0,0}, {0,1,0,0,0,0} };
    cout << solve(matrix) << endl;
}

Đầu vào / Đầu ra

Input: ma trận 6x6
Output: 4