链接: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这个就是一个并查集求联通快
1 #include <cstdio>
2 #include <algorithm>
3 #include <vector>
4 #include <queue>
5 #include <cstring>
6 #include <string>
7 using namespace std;
8 const int maxn = 1e4 + 10;
9
10 typedef long long LL ;
11 int fa[maxn], x[maxn], y[maxn];
12
13 void init(int n) {
14 for (int i = 0 ; i <= n ; i++) {
15 fa[i] = i;
16 }
17 }
18 int find(int p) {
19 while(p != fa[p]) p = fa[p];
20 return p;
21 }
22 int find_set(int p)
23 {
24 while(p!=fa[p]) p=fa[p];
25 return p;
26 }
27
28 void combine(int p, int q) {
29 int np = find_set(p);
30 int nq = find_set(q);
31 if (np != nq) fa[np] = nq;
32 }
33
34 int main() {
35 int n;
36 //freopen("DATA.txt","r",stdin);
37 while(scanf("%d", &n) != EOF) {
38 init(n);
39 for (int i = 1 ; i <= n ; i++) {
40 scanf("%d%d", &x[i], &y[i]);
41 }
42 for (int i = 1 ; i < n ; i++)
43 for (int j = i + 1 ; j <= n ; j++)
44 if (x[i] == x[j] || y[i] == y[j] ) combine(i, j);
45 int ans = 0;
46 for (int i = 1 ; i <= n ; i++)
47 if (fa[i] == i) ans++;
48 printf("%d\n", ans - 1);
49 }
50 return 0;
51 }
原文链接: https://www.cnblogs.com/qldabiaoge/p/8972252.html
欢迎关注
微信关注下方公众号,第一时间获取干货硬货;公众号内回复【pdf】免费获取数百本计算机经典书籍
原创文章受到原创版权保护。转载请注明出处:https://www.ccppcoding.com/archives/273043
非原创文章文中已经注明原地址,如有侵权,联系删除
关注公众号【高性能架构探索】,第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处!