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

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

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

using namespace std;

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

    vector<vector<int>> graph(n + 1); // 罪犯关系图
    vector<int> prison(n + 1, -1); // 监狱分配情况，-1表示未分配

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

    queue<int> q;

    for (int i = 1; i <= n; i++) {
        if (prison[i] == -1) {
            prison[i] = 0;
            q.push(i);

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

                for (int j : graph[curr]) {
                    if (prison[j] == -1) {
                        prison[j] = 1 - prison[curr];
                        q.push(j);
                    } else if (prison[j] == prison[curr]) {
                        cout << "无法满足要求" << endl;
                        return 0;
                    }
                }
            }
        }
    }

    int count = 0;

    for (int i = 1; i <= n; i++) {
        if (prison[i] == -1)
            count++;
    }

    cout << count << endl;

    return 0;
}

该算法使用BFS遍历罪犯关系图，并将罪犯分配到不同的监狱中。如果发现冲突（同一个监狱中的罪犯互相打架），则输出"无法满足要求"。最后统计未分配的罪犯数量并输出。