撰写
Bajtek 正在学习滑冰。他是一个初学者，因此他仅有的滑行模式是从一个雪堆出发，向北、向东、向南或向西滑行，直到抵达另一个雪堆。他已经注意到，以这种方式，不可能从某些雪堆抵达另一些雪堆，无论采用什么样的移动顺序。他现在希望堆积更多的雪堆，以便能够从任意一个雪堆，抵达其它任意的雪堆。请找出还需创建的雪堆的最小数目。
我们假定 Bajtek 只能够在整数坐标的位置堆积雪堆。
输入
输入的第一行包含了单个整数 n (1 ≤ n ≤ 100) — 雪堆的数目。接下来的 n 行中，每行包含两个整数 xi 和 yi (1 ≤ xi, yi ≤ 1000) — 第 i 个雪堆的坐标。
注意：北向与 Oy 轴的方向一致，东向与 Ox 轴的方向一致。所有雪堆的位置都是唯一的。
输出
输出需要创建的雪堆的最小数目，使得 Bajtek 能够从任意一个雪堆到达其它任意一个雪堆。
示例
输入
2 2 1 1 2
输出
1
输入
2 2 1 4 1
输出
0
- 题解
- 在同一行/列皆为连通
- 并查集查找连通块个数
- 增在一个堆相当于增加一条连通两个块的边
- 所以答案为块数-1
- 代码
-
#include<algorithm> #include <iostream> #include <fstream> #include <cstdlib> #include <cstring> #include <cassert> #include <cstdio> #include <vector> #include <string> #include <cmath> #include <queue> #include <stack> #include <set> #include <map> using namespace std; #define P(a,b,c) make_pair(a,make_pair(b,c)) #define rep(i,a,n) for (int i=a;i<=n;i++) #define per(i,a,n) for (int i=n;i>=a;i--) #define CLR(vis) memset(vis,0,sizeof(vis)) #define MST(vis,pos) memset(vis,pos,sizeof(vis)) #define pb push_back #define mp make_pair #define all(x) (x).begin(),(x).end() #define fi first #define se second #define SZ(x) ((int)(x).size()) typedef pair<int,pair<int,int> >pii; typedef long long ll; typedef unsigned long long ull; const ll mod = 1000000007; const int INF = 0x3f3f3f3f; ll gcd(ll a, ll b) { return b ? gcd(b, a%b) : a; } template<class T>inline void gmax(T &A, T B) { (A<B)&&(A=B);//if(B>A)A=B; } template<class T>inline void gmin(T &A, T B) { (A>B)&&(A=B);//if(B<A)A=B; } template <class T> inline bool scan_d(T &ret) { char c; int sgn; if(c=getchar(),c==EOF) return 0; //EOF while(c!='-'&&(c<'0'||c>'9')) c=getchar(); sgn=(c=='-')?-1:1; ret=(c=='-')?0:(c-'0'); while(c=getchar(),c>='0'&&c<='9') ret=ret*10+(c-'0'); ret*=sgn; return 1; } inline void outt(int x) { if(x>9) outt(x/10); putchar(x%10+'0'); } const int maxn = 1e3+10; int vis[maxn]; int pre[maxn]; int find(int x){ return x==pre[x]?x:pre[x]=find(pre[x]); } int x[maxn],y[maxn]; int main(){ int n; cin>>n; rep(i,1,n){ pre[i]=i; cin>>x[i]>>y[i]; } rep(i,1,n){ rep(j,i+1,n){ if(x[i]==x[j]||y[i]==y[j]){ pre[find(i)]=find(j); } } } int ans=0; rep(i,1,n){ if(++vis[find(i)]==1){ ++ans; } } cout<<ans-1<<endl; return 0; }
-