POJ2236 Wireless Network(并查集)

描述

南亚发生了一次地震。ACM (Asia Cooperated Medical 亚洲联合医疗队) 已经为膝上型电脑搭建了一个无线网络，但受到了一次不可预知的余震攻击，因此网络中的所有电脑都被破坏了。电脑被逐台修复，网络逐步恢复了工作。由于受到硬件的约束，每台电脑只能与距离它不超过 d 米的其它电脑直接通信。但每台电脑可被看作其它两台电脑的通信中转点，也就是说，如果电脑 A 和电脑 B 可以直接通信，或存在一台电脑 C 既可与 A 也可与 B 通信，那么电脑 A 和电脑 B 之间就能够通信。

在处理网络修复的过程中，工作人员们在任何一个时刻，可以执行两种操作：维修一台电脑，或测试两台电脑是否能够通信。请您找出全部的测试操作。

输入

第一行包含了两个整数 $N$

“O p” $(1 <= p <= N)$

“S p q” $(1 <= p, q <= N)$

输入不超过 300000 行。

输出

对于每个测试操作，如果两台电脑能够通信，则打印 “SUCCESS”；否则，打印 “FAIL”。

样例

输入

4 1
0 1
0 2
0 3
0 4
O 1
O 2
O 4
S 1 4
O 3
S 1 4

输出

FAIL
SUCCESS

思路

简单的并查集问题，主要是注意处理距离比较问题

为避免因为计算距离的时候出现精度误差，直接d取平方，不进行开方
用use数组标记修过的网络，只有修过的才对其进行更新

代码

  1 /*
  2  * =================================================================
  3  *
  4  *       Filename:  A.cpp
  5  *
  6  *           Link:  http://poj.org/problem?id=2236
  7  *
  8  *        Version:  1.0
  9  *        Created:  2018/09/18 10时15分26秒
 10  *       Revision:  none
 11  *       Compiler:  g++
 12  *
 13  *         Author:  杜宁元 (https://duny31030.top/), duny31030@126.com
 14  *   Organization:  QLU_浪在ACM
 15  *
 16  * =================================================================
 17  */
 18 #include <iostream>
 19 #include <stdio.h>
 20 #include <algorithm>
 21 #include <math.h>
 22 #include <string.h>
 23 using namespace std;
 24 #define clr(a, x) memset(a, x, sizeof(a))
 25 #define rep(i,a,n) for(int i=a;i<=n;i++)
 26 #define pre(i,a,n) for(int i=n;i>=a;i--)
 27 #define ll long long
 28 #define max3(a,b,c) fmax(a,fmax(b,c))
 29 #define ios ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
 30 const double eps = 1e-6;
 31 const int INF = 0x3f3f3f3f;
 32 const int mod = 1e9 + 7;
 33 const int N = 1e4+10;
 34 int f[N],x[N],y[N];
 35 int find(int i) 
 36 {  
 37     if(i!=f[i]) 
 38         f[i]=find(f[i]);  
 39     return f[i];  
 40 }  
 41 int dis(int xx,int yy)
 42 {
 43     int x1 = x[xx]-x[yy];
 44     x1 *= x1;
 45     int x2 = y[xx]-y[yy];
 46     x2 *= x2;
 47     return (x1+x2);
 48 }
 49 int n,d,cx,cy;
 50 int use[N];
 51 int main()
 52 {
 53     ios
 54 #ifdef ONLINE_JUDGE 
 55 #else 
 56         freopen("in.txt","r",stdin);
 57     // freopen("out.txt","w",stdout); 
 58 #endif
 59     // scanf("%d %d",&n,&d);
 60     cin >> n >> d;
 61     clr(use,0);
 62     int t = d*d;
 63     rep(i,1,n)
 64     {
 65         f[i] = i;
 66         // scanf("%d %d",&x[i],&y[i]);
 67         cin >> x[i] >> y[i];
 68     }
 69     char op;
 70     while(cin >> op)
 71     {
 72         if(op == 'O')
 73         {
 74             // scanf("%d",&cx);
 75             cin >> cx;
 76 
 77             use[cx] = 1;
 78             rep(i,1,n)
 79             {
 80                 if(cx != i && use[i] && dis(i,cx) <= t)
 81                 {
 82                     int k1 = find(cx);
 83                     int k2 = find(i);
 84                     if(k1 < k2)
 85                         f[k1] = k2;
 86                     else 
 87                         f[k2] = k1;
 88                 }
 89             }
 90         }
 91         else 
 92         {
 93             // scanf("%d %d",&cx,&cy);
 94             cin >> cx >> cy;
 95             int fx = find(cx);
 96             int fy = find(cy);
 97             if(fx == fy)
 98                 cout << "SUCCESS" << endl;
 99             else 
100                 cout << "FAIL" << endl;
101         }
102     }
103     fclose(stdin);
104     // fclose(stdout);
105     return 0;
106 }