洛谷 P10378 [GESP202403 七级] 交流问题-普及/提高-

题目描述

来自两所学校 $A$、$B$ 的 $n$ 名同学聚在一起相互交流。为了方便起见，我们把这些同学从 $1$ 至 $n$ 编号。他们共进行了 $m$ 次交流，第 $i$ 次交流中，编号为 $u_i,v_i$ 的同学相互探讨了他们感兴趣的话题，并结交成为了新的朋友。

由于这次交流会的目的是促进两校友谊，因此只有不同学校的同学之间会交流。同校同学并不会互相交流。

作为 $A$ 校顾问，你对 $B$ 校的规模非常感兴趣，你希望求出 $B$ 校至少有几名同学、至多有几名同学。

输入格式

第一行两个正整数，表示同学的人数 $n$、交流的次数 $m$。
接下来 $m$ 行，每行两个整数 $u_i,v_i$，表示一次交流。

输出格式

输出一行两个整数，用单个空格隔开，分别表示 $B$ 校至少有几名同学、至多有几名同学。

输入输出样例 #1

输入 #1

4 3
1 2
2 3
4 2

输出 #1

1 3

输入输出样例 #2

输入 #2

7 5
1 2
2 3
4 2
5 6
6 7

输出 #2

2 5

说明/提示

数据规模与约定

• 对 $30\%$ 的数据，保证 $n\le 17$，$m\le 50$。
• 对 $60\%$ 的数据，保证 $n\le 500$，$m\le 2000$。
• 对全部的测试数据，保证 $1\le u_i,v_i\le n\le 10^5$，$1\le m\le 2\times 10^5$，输入是合法的，即交流一定是跨校开展的。

solution

对于每一块一块连通的区域给相邻的节点染不同的两种颜色，统计每种颜色节点的数量。

代码

#include <iostream>
#include "bit"
#include "vector"
#include "unordered_set"
#include "set"
#include "queue"
#include "stack"
#include "algorithm"
#include "bitset"
#include "cstring"using namespace std;int n, m, x, y, cnt[2];
vector<int> e[100001];
bool vis[100001];void dfs(int u, bool col) {cnt[col]++;vis[u] = true;for (int v: e[u]) {if (!vis[v]) {dfs(v, !col);}}
}int main() {cin >> n >> m;for (int i = 0; i < m; i++) {cin >> x >> y;e[x].push_back(y);e[y].push_back(x);}int a = 0, b = 0;for (int i = 1; i <= n; i++) {if (!vis[i]) {dfs(i, false);a += min(cnt[0], cnt[1]);b += max(cnt[0], cnt[1]);cnt[0] = cnt[1] = 0;}}cout << a << " " << b;}

结果