链接: https://www.nowcoder.com/acm/contest/84/C
任意点
时间限制: C/C++ 1 秒, 其他语言 2 秒
空间限制: C/C++ 32768K, 其他语言 65536K
64bit IO Format: %lld
题目描述
平面上有若干个点, 从每个点出发, 你可以往东南西北任意方向走, 直到碰到另一个点, 然后才可以改变方向.
请问至少需要加多少个点, 使得点对之间互相可以到达.
输入描述:
第一行一个整数 n 表示点数 (1 <= n <= 100).
第二行 n 行, 每行两个整数 x
i , y i
表示坐标 ( 1 <= x
i , y i
<= 1000).
y 轴正方向为北, x 轴正方形为东.
输出描述:
输出一个整数表示最少需要加的点的数目.
示例 1
输入
2 2 1 1 2
输出
1
示例 2
输入
2 2 1 4 1
输出
0
这个就是一个并查集求联通快
- #include <cstdio>
- #include <algorithm>
- #include <vector>
- #include <queue>
- #include <cstring>
- #include <string>
- using namespace std;
- const int maxn = 1e4 + 10;
- typedef long long LL ;
- int fa[maxn], x[maxn], y[maxn];
- void init(int n) {
- for (int i = 0 ; i <= n ; i++) {
- fa[i] = i;
- }
- }
- int find(int p) {
- while(p != fa[p]) p = fa[p];
- return p;
- }
- int find_set(int p)
- {
- while(p!=fa[p]) p=fa[p];
- return p;
- }
- void combine(int p, int q) {
- int np = find_set(p);
- int nq = find_set(q);
- if (np != nq) fa[np] = nq;
- }
- int main() {
- int n;
- //freopen("DATA.txt","r",stdin);
- while(scanf("%d", &n) != EOF) {
- init(n);
- for (int i = 1 ; i <= n ; i++) {
- scanf("%d%d", &x[i], &y[i]);
- }
- for (int i = 1 ; i < n ; i++)
- for (int j = i + 1 ; j <= n ; j++)
- if (x[i] == x[j] || y[i] == y[j] ) combine(i, j);
- int ans = 0;
- for (int i = 1 ; i <= n ; i++)
- if (fa[i] == i) ans++;
- printf("%d\n", ans - 1);
- }
- return 0;
- }
来源: https://www.cnblogs.com/qldabiaoge/p/8972252.html