简答题 偏难
#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

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

数据规模

对于30的测试点,保证N≤17,M≤50;

对于60的测试点,保证N≤500,M≤2000;

对于100的测试点,保证N≤105,M≤2×105。

未登录也能判分,登录后才会记录
答案与解析
正确答案:<pre class="brush:cpp;toolbar:false">#include &lt;iostream&gt; #include &lt;vector&gt; #include &lt;unordered_map&gt; using namespace std; void dfs(vector&lt;vector&lt;int&gt;&gt;&amp; graph, int node, vector&lt;int&gt;&amp; 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&lt;int, int&gt; find_b_school_students(int N, vector&lt;pair&lt;int, int&gt;&gt;&amp; connections) { vector&lt;vector&lt;int&gt;&gt; graph(N + 1); for (const auto&amp; connection : connections) { graph[connection.first].push_back(connection.second); graph[connection.second].push_back(connection.first); } vector&lt;int&gt; colors(N + 1, -1); int min_ans = 0; for (int i = 1; i &lt;= 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 &gt;&gt; N &gt;&gt; M; vector&lt;pair&lt;int, int&gt;&gt; connections(M); for (int i = 0; i &lt; M; ++i) { cin &gt;&gt; connections[i].first &gt;&gt; connections[i].second; } pair&lt;int, int&gt; b_students = find_b_school_students(N, connections); cout &lt;&lt; b_students.first &lt;&lt; " " &lt;&lt; b_students.second &lt;&lt; endl; return 0; }</pre>
这道题暂未补解析。