POJ 2236 Wireless Network(並查集)

POJ 2236 Wireless Network(並查集)

題意

有n台損壞的電腦，現要將其逐台修復，且使其相互恢復通信功能。若兩台電腦能相互通信，則有兩種情況，一是他們之間的距離小於d，二是他們可以借助都可到達的第三台已修復的電腦。給出所有電腦的坐標位置，對其進行兩種可能的操作，O x表示修復第x台，S x y表示判斷x y之間能否通信，若能輸出SUCCESS，否則輸出FALL。

思路

用並查集來保存電腦互相的連通情況。
每次修好電腦後，將它可以通信的電腦(距離滿足且已修好)與它進行連通。

代碼

#include
#include
#include
#include
#include
#include
#define LL long long
using namespace std;

const int N = 1009;
int x[N], y[N], fa[N];
bool p[N];
vector v[N];

int find(int x)
{
    if(fa[x] == x)
        return x;
    return fa[x] = find(fa[x]);
}

int main()
{
    int n, d;
    char s[2];
    scanf("%d%d", &n, &d);
    for(int i=1; i<=n; i++)
    {
        scanf("%d%d", &x[i], &y[i]);
        fa[i] = i;
    }
    for(int i=1; i<=n; i++)
        for(int j=i+1; j<=n; j++)
        {
            if(((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j])) <= d*d)
            {
                v[j].push_back(i);
                v[i].push_back(j);
            }
        }
    while(~scanf("%s", s))
    {
        int a, b;
        if(s[0] == 'O')
        {
            scanf("%d", &a);
            p[a] = true;
            for(int i=0; i