简答题
偏难
#21428
交流问题 问题描述 来自2所学校A校、B校的N名同学相聚在一起相互交流,方便起见,我们把这些同学从1至N编号。他们共进行了M次交流,第i次交流中,编号为u i…
交流问题
问题描述
来自2所学校A校、B校的N名同学相聚在一起相互交流,方便起见,我们把这些同学从1至N编号。他们共进行了M次交流,第i次交流中,编号为ui,vi的同学相互探讨了他们感兴趣的话题,并结交成为了新的朋友。
由于这次交流会的目的是促进两校友谊,因此只有不同学校的同学之间会交流,同校同学并不会相互交流。
作为 A 校顾问,你对 B 校的规模非常感兴趣,你希望求出 B 校至少有几名同学、至多有几名同学。
输入描述
第一行两个正整数N,M,表示同学的人数,交流的次数。
接下来M行,每行两个正整数ui,vi,表示一次交流。
题目保证输入合法,即交流一定是跨校开展的。
输出描述
输出一行两个整数,用单个空格隔开,分别表示 B 校至少有几名同学、至多有几名同学。
特别提醒
在常规程序中,输入、输出时提供提示是好习惯。但在本场考试中,由于系统限定,请不要在输入、输出中附带任何提示信息。
样例输入 1
样例输出 1
样例输入 2
样例输出 2
数据规模
对于30的测试点,保证N≤17,M≤50;
对于60的测试点,保证N≤500,M≤2000;
对于100的测试点,保证N≤105,M≤2×105。
答案与解析
正确答案:<pre class="brush:cpp;toolbar:false">#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;
}</pre>
这道题暂未补解析。