T^T的图论
TimeLimit:3000MS MemoryLimit:256MB
64-bit integer IO format:%lld
Problem Description
有一个坐标系，坐标系上有n个点，在同一行或同一列上的任意两点称为关联的，并且关联属性是可传递的，即A和B关联，B和C关联，则可认为A和C关联，现在问图中是否任意两点都是关联的。
Input
n>=2 && n<=50万
每个点的坐标x、y满足 1<=x、y<=50000
Output
如果是关联的，输出YES，否则，输出NO
SampleInput
NO YES
分析：根据题目我们需要把具有x和y任选其一相同的，合并在一个集合中
一开始想的是先把所有的点按x的大小进行排序，相同的点合并到一个集合中
再把所有的点按y的大小进行排序，相同的点合并道一个集合中
这样的话刚刚可以在时间限制内卡过去 2900多MS
代码如下:
#include <cstdio> #include <iostream> #include <cstring> #include <algorithm> #include <vector> #include <queue> #include <vector> #include <stack> using namespace std; const int MAXN=5e5+10; int pre[MAXN]; int num[MAXN]; struct node { int x; int y; int id; }poi[MAXN]; int cmp1(node a,node b) { return a.x<b.x; } int cmp2(node a,node b) { return a.y<b.y; } int Find(int x) { int h,tem; h=x; while(x!=pre[x]) x=pre[x]; while(h!=x) { tem=pre[h]; pre[h]=x; h=tem; } return x; } void join(int x,int y) { int p=Find(x); int q=Find(y); if(p!=q) { pre[p]=q; num[q]=num[p]+num[q]; } } int main() { int n; while(scanf("%d",&n)!=EOF) { for(int i=0;i<n;i++){ pre[i]=i; num[i]=1; } for(int i=0;i<n;i++) { scanf("%d%d",&poi[i].x,&poi[i].y); poi[i].id=i; } sort(poi,poi+n,cmp1); for(int i=1;i<n;i++) { if(poi[i].x==poi[i-1].x) join(poi[i-1].id,poi[i].id); } sort(poi,poi+n,cmp2); for(int i=1;i<n;i++) { if(poi[i].y==poi[i-1].y) join(poi[i-1].id,poi[i].id); } if(num[Find(0)]==n)puts("YES"); else puts("NO"); } return 0; }
看了其他人的代码后发现,可以先对于x的话，统计集合的数量，如果这个x值第一次出现，那么集合必增加。如果已经出现过，那么就能合并到已经出现的集合里面
然后将y排序，y值相同的点，再去看它们的x值是否已经合并到了一个集合，如果不在一个集合，就将它们合并到一个集合里，并且集合的数量减一.
（在这里，我们是根据x的值进行并查集，那么一个开始x值相同的就自动到了一个集合，这种方法可以减少进行集合合并的次数，并节约时间）
代码如下：
#include <cstdio> #include <iostream> #include <cstring> #include <algorithm> #include <vector> #include <queue> #include <vector> #include <stack> using namespace std; const int MAXN=5e5+10; int pre[MAXN]; int ans; int vis[MAXN]; struct node { int x; int y; int id; }poi[MAXN]; int cmp1(node a,node b) { return a.x<b.x; } int cmp2(node a,node b) { return a.y<b.y; } int Find(int x) { int h,tem; h=x; while(x!=pre[x]) x=pre[x]; while(h!=x) { tem=pre[h]; pre[h]=x; h=tem; } return x; } void join(int x,int y) { int p=Find(x); int q=Find(y); if(p!=q) { pre[p]=q; ans--; } } int main() { int n,x1,x2; while(scanf("%d",&n)!=EOF) { memset(vis,0,sizeof(vis)); for(int i=1;i<=50000;i++) pre[i]=i; ans=0; for(int i=0;i<n;i++) scanf("%d%d",&poi[i].x,&poi[i].y); for(int i=0;i<n;i++) { if(!vis[poi[i].x]) { vis[poi[i].x]=1; ans++; } } sort(poi,poi+n,cmp2); for(int i=1;i<n;i++) { if(poi[i].y==poi[i-1].y) { join(poi[i].x,poi[i-1].x); } } if(ans>1)puts("NO"); else puts("YES"); } return 0; } /*4 1 3 4 5 5 3 4 3 NO */