有n个罪犯，其中有m对罪犯在同一个监狱会互相打架（每个罪犯最多会与其他2个罪犯打架 ）。 已知 m 对相互打架罪犯的信息，要将所有罪犯分配到A和B两个监狱中（要求两个监狱的罪犯人数相等且同一个监狱中的罪犯不能互相打架）。 为了满足上述的要求，有些罪犯不得不被安排到其他的监狱中。 求出最少被安排到其他的监狱的罪犯数量。输入：第一行，两个整数 n和m接下来m行，每行两个整数a 和b 表示罪犯a与罪犯b在同一个监狱会相互打架。输出：一个整数，表示最少的罪犯人数，如果没有，输出0。 C++建议代码

以下是一个用C++编写的解决方案：

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

bool isBipartite(vector<vector<int>>& graph, vector<int>& colors, int start) {
    queue<int> q;
    q.push(start);
    colors[start] = 0;

    while (!q.empty()) {
        int curr = q.front();
        q.pop();

        for (int neighbor : graph[curr]) {
            if (colors[neighbor] == -1) {
                colors[neighbor] = 1 - colors[curr];
                q.push(neighbor);
            } else if (colors[neighbor] == colors[curr]) {
                return false;
            }
        }
    }

    return true;
}

int minAdditionalPrisoners(vector<vector<int>>& conflicts) {
    int n = conflicts.size();
    vector<vector<int>> graph(n);
    vector<int> colors(n, -1);

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (i != j && conflicts[i][j] == 1) {
                graph[i].push_back(j);
                graph[j].push_back(i);
            }
        }
    }

    int minPrisoners = 0;

    for (int i = 0; i < n; i++) {
        if (colors[i] == -1 && !isBipartite(graph, colors, i)) {
            minPrisoners++;
        }
    }

    return minPrisoners;
}

int main() {
    int n, m;
    cin >> n >> m;

    vector<vector<int>> conflicts(n, vector<int>(n, 0));

    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        conflicts[a][b] = 1;
        conflicts[b][a] = 1;
    }

    int minPrisoners = minAdditionalPrisoners(conflicts);
    cout << minPrisoners << endl;

    return 0;
}

该算法首先将冲突信息构建成罪犯关系图。然后使用BFS来判断罪犯是否可以被正确分配到两个监狱中，即是否为二分图。如果存在冲突，即不是二分图，则需要将冲突的罪犯安排到其他监狱中，即需要额外安排的罪犯数量加一。最后输出最少需要安排的罪犯数量。