每日一题《交流问题》
2025-10-22 18:40:08
发布于：浙江
5阅读
0回复
0点赞
题目描述
#include <iostream>
#include <vector>
#include <queue>
#include <climits>
using namespace std;
const int MOD = 1e9 + 7;
const int UNCOLORED = -1; // 表示未染色
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
cin >> n >> m;
// 1. 构建邻接表
vector<vector<int>> adj(n + 1); // 顶点编号从1到n
for (int i = 0; i < m; ++i) {
int u, v;
cin >> u >> v;
adj[u].push_back(v);
adj[v].push_back(u);
}
// 2. 初始化颜色数组，所有顶点初始为未染色
vector<int> color(n + 1, UNCOLORED);
int min_b = 0, max_b = 0; // B校人数的最小值和最大值
// 3. 遍历所有顶点，处理每个连通分量
for (int i = 1; i <= n; ++i) {
if (color[i] == UNCOLORED) { // 如果当前顶点未染色，说明是一个新的连通分量
queue<int> q;
q.push(i);
color[i] = 0; // 将当前顶点染为颜色0
int count0 = 1, count1 = 0; // 该连通分量中颜色0和颜色1的顶点数
// BFS遍历该连通分量
while (!q.empty()) {
int u = q.front();
q.pop();
// 遍历u的所有邻居
for (int v : adj[u]) {
if (color[v] == UNCOLORED) { // 如果邻居未染色
color[v] = color[u] ^ 1; // 染成与u相反的颜色（0^1=1, 1^1=0）
if (color[v] == 0) {
count0++;
} else {
count1++;
}
q.push(v);
}
// 题目保证输入合法（是二分图），因此不需要处理染色冲突的情况
}
}
// 4. 更新B校人数的最小值和最大值
min_b += min(count0, count1);
max_b += max(count0, count1);
}
}
// 5. 输出结果
cout << min_b << " " << max_b << endl;
return 0;
}
这里空空如也
有帮助，赞一个