CCF GESP 2024年3月认证 C++ 7级
题目描述
来自两所学校 $A$、$B$ 的 $n$ 名同学聚在一起相互交流。为了方便起见，我们把这些同学从 $1$ 至 $n$ 编号。他们共进行了 $m$ 次交流，第 $i$ 次交流中，编号为 $u_i, v_i$ 的同学相互探讨了他们感兴趣的话题，并结交成为了新的朋友。
由于这次交流会的目的是促进两校友谊，因此只有不同学校的同学之间会交流。同校同学并不会互相交流。
作为 $A$ 校顾问，你对 $B$ 校的规模非常感兴趣，你希望求出 $B$ 校至少有几名同学、至多有几名同学。
输入格式
第一行两个正整数，表示同学的人数 $n$、交流的次数 $m$。
接下来 $m$ 行，每行两个整数 $u_i, v_i$，表示一次交流。
题目保证输入合法，即交流一定是跨校开展的。
输出格式
输出一行两个整数，用单个空格隔开，分别表示 $B$ 校至少有几名同学、至多有几名同学。
特别提醒
在常规程序中，输入、输出时提供提示是好习惯。但在本场考试中，由于系统限定，请不要在输入、输出中附带任何提示信息。
样例说明
样例 1
4 3
1 2
2 3
4 21 3样例 2
7 5
1 2
2 3
4 2
5 6
6 72 5数据范围
对于 $30\%$ 的测试点 ，保证 $n \leq 17$，$m \leq 50$。
对于 $60\%$ 的测试点 ，保证 $n \leq 500$，$m \leq 2000$。
对于全部的测试点 ，保证 $n \leq 10^5$， $m \leq 2\times 10^5$。
题目描述
小杨同学用不同种类的俄罗斯方块填满了一个大小为 $n \times m$ 的网格图。
网格图由 $n \times m$ 个带颜色方块构成。小杨同学现在将这个网格图交给了你，请你计算出网格图中俄罗斯方块的种类数。
如果两个同色方块是四连通（即上下左右四个相邻的位置）的，则称两个同色方块直接连通；若两个同色方块同时与另一个同色方块直接或间接连通，则称两个同色方块间接连通。一个俄罗斯方块由一个方块和所有与其直接或间接连接的同色方块组成。定义两个俄罗斯方块的种类相同当且仅当通过平移其中一个俄罗斯方块可以和另一个俄罗斯方块重合；如果两个俄罗斯方块颜色不同，仍然视为同一种俄罗斯方块。
例如，在如下情况中，方块 $1$ 和方块 $2$ 是同一种俄罗斯方块，而方块 $1$ 和方块 $3$ 不是同一种俄罗斯方块。
方块1： 方块2： 方块3：
1 1 1 2 2 2 1
1 1 2 2 1 1
1 1输入格式
第一行包含两个正整数 $n$ 和 $m$，表示网格图的大小。
对于之后的 $n$ 行，第 $i$ 行包含 $m$ 个正整数 $a_{i1}, a_{i2}, \dots a_{im}$，表示该行 $m$ 个方块的颜色。
输出格式
输出一个非负整数，表示俄罗斯方块的种类数。
样例说明
样例 1
5 6
1 2 3 4 4 5
1 2 3 3 4 5
1 2 2 3 4 5
1 6 6 7 7 8
6 6 7 7 8 877 种类型的俄罗斯方块如下：
数据范围
对于全部数据，保证有 $1 \leq n, m \leq 500$，$0 \leq a_{i,j} \leq 500^2$。