A33177. 交流问题问题描述来自 2 所学校 A 校、B 校的 名同学相聚在一起相互交流，方便起见，我们把这些同学从 1 至 N 编号。他们共进行了 M 次交流，第 次交流中，编号为 ui , vi 的同学相互探讨了他们感兴趣的话题，并结交成为了新的朋友。由于这次交流会的目的是促进两校友谊，因此只有不同学校的同学之间会交流，同校同学并不会相互交流。作为 A 校顾问，你对 B 校的规模非常感兴趣，你希望求出 …
填空题
困难
知识点
题目描述
交流问题
问题描述
来自 2 所学校 A 校、B 校的 名同学相聚在一起相互交流，方便起见，我们把这些同学从 1 至 N 编号。他们共进行了 M 次交流，第 次交流中，编号为 ui , vi 的同学相互探讨了他们感兴趣的话题，并结交成为了新的朋友。
由于这次交流会的目的是促进两校友谊，因此只有不同学校的同学之间会交流，同校同学并不会相互交流。作为 A 校顾问，你对 B 校的规模非常感兴趣，你希望求出 B 校至少有几名同学、至多有几名同学。
输入描述
第一行两个正整数 N , M，表示同学的人数，交流的次数。
接下来 M 行，每行两个正整数 ui , vi，表示一次交流。
题目保证输入合法，即交流一定是跨校开展的。
输出描述
输出一行两个整数，用单个空格隔开，分别表示 B 校至少有几名同学、至多有几名同学。
特别提醒
在常规程序中，输入、输出时提供提示是好习惯。但在本场考试中，由于系统限定，请不要在输入、输出中附带任何提示信息。
样例输入 1
4 3
1 2
2 3
4 2样例输出 1
1 3样例输入 2
7 5
1 2
2 3
4 2
5 6
6 7样例输出 2
2 5参考答案
#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;
void dfs(vector<vector<int>>& graph, int node, vector<int>& colors, int* color_cnt,
int curr_color) {
colors[node] = curr_color;
color_cnt[curr_color]++;
for (int neighbor : graph[node]) {
if (colors[neighbor] == -1) {
dfs(graph, neighbor, colors, color_cnt, curr_color ^ 1);
}
}
}
pair<int, int> find_b_school_students(int N, vector<pair<int, int>>& connections) {
vector<vector<int>> graph(N + 1);
for (const auto& connection : connections) {
graph[connection.first].push_back(connection.second);
graph[connection.second].push_back(connection.first);
}
vector<int> colors(N + 1, -1);
int min_ans = 0;
for (int i = 1; i <= N; ++i) {
if (colors[i] == -1) {
int color_cnt[2] = {
0, 0
}
;
dfs(graph, i, colors, color_cnt, 0);
min_ans += min(color_cnt[0], color_cnt[1]);
}
}
return make_pair(min_ans, N - min_ans);
}
int main() {
int N, M;
cin >> N >> M;
vector<pair<int, int>> connections(M);
for (int i = 0; i < M; ++i) {
cin >> connections[i].first >> connections[i].second;
}
pair<int, int> b_students = find_b_school_students(N, connections);
cout << b_students.first << " " << b_students.second << endl;
return 0;
}
上一题
下一题