Problem Description有一个坐标系，坐标系上有n个点，在同一行或同一列上的任意两点称为关联的，并且关联属性是可传递的，即A和B关联，B和C关联，则可认为A和C关联，现在问图中是否任意两点都是关联的。
Inputn>=2 && n<=50万
每个点的坐标x、y满足 1<=x、y<=50000
Output如果是关联的，输出YES，否则，输出NO
SampleInput2 1 1 3 3 3 1 1 1 3 3 3SampleOutputNO YES
一开始超时了
#include<cstdio> using namespace std; const int maxn=6000000; int pre[maxn]; struct Node { int x,y; } node[maxn]; int find(int x) { int r=x; while(r!=pre[r]) r=pre[r]; int i=x,j; while(pre[i]!=r) { j=pre[i]; pre[i]=r; i=j; } return r; } int join(int x,int y) { int fx=find(x),fy=find(y); if(fx!=fy) pre[fx]=fy; } int main() { int n,x,y; while(~scanf("%d",&n)) { for(int i=1; i<=n; i++) pre[i]=i; for(int i=1; i<=n; i++) { scanf("%d%d",&node[i].x,&node[i].y); for(int j=1; j<i; j++) if(node[i].x==node[j].x||node[i].y==node[j].y) join(i,j); } int p=find(1),flag=1; for(int i=2; i<=n; i++) { if(p!=find(i)){ flag=0; break; } } if(flag)puts("YES"); else puts("NO"); } return 0; }
后来分别对x,y排序，这样x，y相同的就会聚在一起，卡时间AC了
#include<cstdio> #include<algorithm> using namespace std; const int maxn=6000000; int pre[maxn]; struct Node { int index,x,y; } node[maxn]; bool cmp1(Node a,Node b) { return a.x<b.x; } bool cmp2(Node a,Node b) { return a.y<b.y; } int find(int x) { int r=x; while(r!=pre[r]) r=pre[r]; int i=x,j; while(pre[i]!=r) { j=pre[i]; pre[i]=r; i=j; } return r; } int join(int x,int y) { int fx=find(x),fy=find(y); if(fx!=fy) pre[fx]=fy; } int main() { int n,x,y; while(~scanf("%d",&n)) { for(int i=1; i<=n; i++) pre[i]=i; for(int i=1; i<=n; i++) { node[i].index=i; scanf("%d%d",&node[i].x,&node[i].y); } /// 对x排序 sort(node+1,node+n+1,cmp1); for(int i=2;i<=n;i++) { if(node[i].x==node[i-1].x) { join(node[i].index,node[i-1].index); } } /// 对Y排序 sort(node+1,node+n+1,cmp2); for(int i=2;i<=n;i++) { if(node[i].y==node[i-1].y) { join(node[i].index,node[i-1].index); } } int p=find(1),flag=1; ///找1的祖先应该 find(1),而不是 pre[1],pre[]是给find函数用的 for(int i=2; i<=n; i++) { if(p!=find(i)) { flag=0; break; } } if(flag)puts("YES"); else puts("NO"); } return 0; }