任意点
任意点
https://ac.nowcoder.com/acm/problem/15808
题意
平面上有若干个点，从每个点出发，你可以往东南西北任意方向走，直到碰到另一个点，然后才可以改变方向。
请问至少需要加多少个点，使得点对之间互相可以到达。
输入描述
第一行一个整数n表示点数（ 1 <= n <= 100)。
第二行n行，每行两个整数xi, yi表示坐标（ 1 <= xi, yi <= 1000)。
y轴正方向为北，x轴正方形为东。
输出描述
输出一个整数表示最少需要加的点的数目。
解析
这个题目不难，也是一个裸的并查集，不过有一点隐晦，下面解释一下
首先他只能撞到一个点才能停，看这个图
可以看到1234都是可以相互联系的，而5是独立出来的一个点，要是想要到达5，就要在12或者24之间加一个点，所以这个像什么，就是两个独立的连通块，这样子就很明显是一个并查集了
这个并查集是当x相同或者y相同的时候，就可以插入在一个块里面
代码
#pragma GCC target("avx,sse2,sse3,sse4,popcnt")
#pragma GCC optimize("O2,O3,Ofast,inline,unroll-all-loops,-ffast-math")
#include <bits/stdc++.h>
using namespace std;
#define js ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)
#define all(vv) vv.begin(), vv.end()
typedef long long ll; typedef unsigned long long ull; typedef long double ld;
const ll MOD = 100000000;
inline ll read() { ll s = 0, w = 1; char ch = getchar(); for (; !isdigit(ch); ch = getchar()) if (ch == '-') w = -1; for (; isdigit(ch); ch = getchar()) s = (s << 1) + (s << 3) + (ch ^ 48); return s * w; }
inline void write(ll x) { if (!x) { putchar('0'); return; } char F[40]; ll tmp = x > 0 ? x : -x; if (x < 0)putchar('-'); int cnt = 0; while (tmp > 0) { F[cnt++] = tmp % 10 + '0'; tmp /= 10; } while (cnt > 0)putchar(F[--cnt]); }
inline ll gcd(ll x, ll y) { return y ? gcd(y, x % y) : x; }
ll qpow(ll a, ll b) { ll ans = 1; while (b) { if (b & 1) ans *= a; b >>= 1; a *= a; } return ans; } ll qpow(ll a, ll b, ll mod) { ll ans = 1; while (b) { if (b & 1)(ans *= a) %= mod; b >>= 1; (a *= a) %= mod; }return ans % mod; }
inline int lowbit(int x) { return x & (-x); }
const int MAXN=105;
ll fa[MAXN];
struct node{
ll x,y;
}a[MAXN];
ll find(ll x){
return x==fa[x]?x:(fa[x]=find(fa[x]));
}
void merge(ll a,ll b){
ll fx=find(a),fy=find(b);
if(fx!=fy) fa[fy]=fx;
}
void init(ll n){
for(ll i=1;i<=n;++i){
fa[i]=i;
}
}
int main(void){
ll n=read();
for(ll i=1;i<=n;++i){
a[i].x=read();
a[i].y=read();
}
init(n);
for(ll i=1;i<=n;++i){
for(ll j=1;j<=n;j++){
if(a[i].x==a[j].x||a[i].y==a[j].y)
merge(i,j);
}
}
ll ans=0;
for(ll i=1;i<=n;++i){
if(fa[i]==i)
ans++;
}
write(ans-1);
cout<<endl;
return 0;
}
查看5道真题和解析
