题目链接：题目传送门 大意： 东东成为了快递员，现在有N个人需要送快递，由于他的车出了毛病，从平面直角坐标系上看，他只能朝上、下、左、右四个方向移动。于是他想造一些中转站，使得他可以顺利从某个人的家到达其他任意一个人的家，输出需要建造中转站的最小值。 所有人居住的坐标均为整数。 输入： 第一行包含一个整数N（1<=N<=100）表示需要送快递的人数，接下来N行，每行两个整数Xi，Yi（1<=Xi，Yi<=1000），表示第i个人居住的坐标。 输出： 需要建造的中转站的最小值，使得东东可以从任意一个人的地址到达其他任意人居住的地方。 Input1
2 2 1 1 2Output1
1思路： 将能够相互到达的放在一个集合，用并查集来查找，我比赛时就没写出来 代码：
#include<iostream> #include<set> #include<vector> #include<queue> #include<string.h> #include<algorithm> #include<stack> #include<map> using namespace std; typedef long long int ll; const ll N=1e5+10; int x[N],y[N],f[N]; void init() { for(int i=0;i<=N;i++) { f[i]=i; } } int find(int x) { if(x==f[x]) { return x; } else return f[x]=find(f[x]); }//路径压缩 void merge(int x,int y) { int a=find(x); int b=find(y); if(a!=b) { f[a]=b; } } int main() { ios::sync_with_stdio(false); int n; cin>>n; init(); for(int i=1;i<=n;i++) { cin>>x[i]>>y[i]; } for(int i=1;i<=n;i++) { for(int j=1;j<=n;j++) { if(i==j)continue; if(x[i]==x[j]||y[i]==y[j]) { merge(i,j); }//连接 } } int ans=0; for(int i=1;i<=n;i++) { if(f[i]==i)ans++; } cout<<ans-1; return 0; } /**/