Wireless Network POJ - 2236 并查集 坐标点的转换

  1 #include <cstdio>
  2 #include <fstream>
  3 #include <algorithm>
  4 #include <cmath>
  5 #include <deque>
  6 #include <vector>
  7 #include <queue>
  8 #include <string>
  9 #include <cstring>
 10 #include <map>
 11 #include <stack>
 12 #include <set>
 13 #include <sstream>
 14 #include <iostream>
 15 #define mod 998244353
 16 #define eps 1e-6
 17 #define ll long long
 18 #define INF 0x3f3f3f3f
 19 using namespace std;
 20 
 21 //记录计算机的坐标
 22 struct node
 23 {
 24     int x,y;
 25 };
 26 node no[1005];
 27 //保存能与与第x个计算机相连的计算机
 28 vector<int> ve[1005];
 29 //保存该计算机是否被修复
 30 bool vis[1005];
 31 
 32 //fa[x]表示x的最远祖先
 33 int fa[50002];
 34 //初始化，一开始每个点单独成集合
 35 void build(int qwq) 
 36 {
 37     for(int i=1;i<=qwq;i++)
 38     {
 39         fa[i]=i;
 40     }
 41     return ;
 42 } 
 43 //找到x的最远祖先，并且压缩路径
 44 int find(int x)
 45 {
 46     if(fa[x]==x)
 47     {
 48         return x;
 49     }
 50     return fa[x]=find(fa[x]);
 51 }
 52 //判断x,y是不是在同一个集合里，直接判断最远祖先是不是一样的 
 53 bool che(int x,int y)
 54 {
 55     return find(x)==find(y);
 56 }
 57 //合并x,y，我们在判断x和y是不是同一个集合里，
 58 //路径压缩之后fa[x],fa[y]已经是最远祖先了，
 59 //所以直接将fa[x]的父亲连接在fa[y]的祖先上
 60 void mer(int x,int y)
 61 {
 62     if(!che(x,y)) 
 63     {
 64         fa[fa[x]]=fa[y];
 65     }
 66     return ;
 67 }
 68 int distan(node a,node b)
 69 {
 70     return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);
 71 }
 72 //修复计算机x并将集合x与和x相连的集合合并
 73 void updata(int x)
 74 {
 75     vis[x]=true;
 76     for(int i=0;i<ve[x].size();i++)
 77     {
 78         //与x相连的点
 79         int y=ve[x][i];
 80         //如果y点被唤醒则合并x与y
 81         if(vis[y]&&!che(x,y))
 82         {
 83             mer(x,y);
 84         }
 85     }
 86 }
 87 int main()
 88 {
 89     int n,d;
 90     scanf("%d %d",&n,&d);
 91     //初始化信息
 92     build(n);
 93     //记录点的信息
 94     for(int i=1;i<=n;i++)
 95     {
 96         scanf("%d %d",&no[i].x,&no[i].y);
 97     }
 98     //遍历判断哪些点之间能连接在一起
 99     for(int i=1;i<=n;i++)
100     {
101         for(int j=i+1;j<=n;j++)
102         {
103             if(distan(no[i],no[j])<=d*d)
104             {
105                 ve[i].push_back(j);
106                 ve[j].push_back(i);
107             }
108         }
109     }
110     char ch;
111     int a,b;
112     while(scanf("%c",&ch)!=EOF)
113     {
114         if(ch==‘O‘)
115         {
116             scanf("%d",&a);
117             updata(a);
118         }
119         else if(ch==‘S‘)
120         {
121             scanf("%d %d",&a,&b);
122             //当两个点的祖先一样时表示两点能连接在一起
123             if(find(a)==find(b))
124             {
125                 printf("SUCCESS\n");
126             }
127             else
128             {
129                 printf("FAIL\n");
130             }
131         }
132     }
133 }