描述

我们知道，四川省是我国地震的高发地带，某天在四川省某地发生了一次大地震。ACM (Asia Cooperated Medical 亚洲联合通讯医疗队) 已经为四川省的各移动基站搭建了一个无线通讯网络，但受到了一次不可预知的地震攻击，网络中的所有基站都被破坏了。通过维修工人的不懈努力，基站正在被逐台修复，通信网络也正在逐步恢复工作。由于受到实际情况的约束，一台基站只能与距离它不超过 d 米的其它基站直接通信。但每台基站可以被看作其它两台基站的通信中转点，也就是说，如果基站 A 和基站 B 可以直接通信，或存在一台基站 C 既可与 A 也可与 B 通信，那么基站 A 和基站 B 之间就能够通信。

在处理基站无线通讯网络修复的过程中，工作人员在任何一个时刻，都可以执行以下两种操作：维修一台基站，或测试两台基站是否能够正常通信。请您对于全部的测试操作，判断这两台基站的实时通讯状况；并且在工作人员的工作全部完成之后，判断整个通讯网络之间所有基站是否均可以互相正常通信，若不能，则输出整个通信网络被分割成的互不联通的通信区域个数，以及所有互相联通的通信区域中的最多的基站数量。

输入

单组数据，第一行包含了两个整数 N 和 d (1 <= N <= 10001, 0 <= d <= 20000)。此处 N 是区域内所有基站的数目，编号从 1 到 N；同时，D 是两台基站之间能够直接通信的最大距离。接下来的 N 行，每行包含两个整数 xi, yi (0 <= xi, yi <= 10000)，表示 N 台基站的坐标。从第 (N+1) 行到EOF输入结束，是逐一执行的操作，每行包含一项操作，本题保证所有测试数据中至少包含下列一项操作，格式是以下两者之一：

1. “O p” (1 <= p <= N)，表示维护基站 p 。

2. “S p q” (1 <= p, q <= N)，表示测试基站 p 和 q 是否能够通信。

输出

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

所有操作执行结束后，若区域内所有基站均可互相通信，则在一行内打印 “ALL CONNECTED”；否则，输出两个整数 X 和 Y，分别表示整个通信网络被分割成的互不联通的通信区域个数，以及所有互相联通的通信区域中的最多的基站数量。

样例输入

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
ALL CONNECTED

思路

对于每个输入的操作，
若cz为‘O’ 代表维修，读取基站编号，将其工作状态设为1（已维修），再检查与p基站距离不超过d的其他已维修基站，并将他们合并带同一个集合中
若维修操作“S”，读取两个基站编号p、q，若他们在同一个集合（即find(p) == find(q)），则输出"SUCCESS"，表示它们可以通信；否则输出"FAIL"。

code

#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
#include<vector>
#include<algorithm>
#include<map>
using namespace std;
const int maxn = 1e5 + 10;
typedef long long ll;
#define D(x1,x2) (x1-x2)*(x1-x2)
int pre[maxn];
struct Station {
    ll x, y;
    int work;//1代表已维修好，可以工作
}station[maxn];

void init() {
    for (int i = 1; i < maxn; i++) {
        pre[i] = i;
    }
}
int find(int x) {
    return pre[x] == x ? x : pre[x] = find(pre[x]);
}
void merge(int x, int y) {
    int rootx = find(x);
    int rooty = find(y);
    if (rootx != rooty) {
        pre[rootx] = rooty;
    }

}

int main()
{
    ll n, d;
    while (scanf("%lld%lld", &n, &d) != EOF) {//n为电脑数,d为通信最小距离
        for (int i = 1; i <= n; i++) {
            scanf("%d%d", &station[i].x, &station[i].y);
            station[i].work = 0;
        }
        char cz[2];
        init();
        while (scanf("%s", cz) != EOF) {
            if (cz[0] == 'O') {//维修
                int p;
                scanf("%d", &p);
                station[p].work = 1;
                for (int i = 1; i <= n; i++) {
                    ll deltx = D(station[i].x, station[p].x);
                    ll delty = D(station[i].y, station[p].y);
                    if (i != p && station[i].work == 1 && (deltx + delty <= d * d)) {
                        merge(p, i);
                    }
                }
            }
            else {
                int p, q;
                scanf("%d%d", &p, &q);
                if (find(p) == find(q)) {
                    printf("SUCCESS\n");
                }
                else {
                    printf("FAIL\n");
                }
            }
        }
        map<int, int> mp;//统计集合的大小
            for (int i = 1; i <= n; i++) {
                mp[find(i)]++;
            }
            int maxsize = 0;
            for (auto iter : mp) {
                maxsize = max(maxsize, iter.second);
            }
            if (mp.size() == 1) {
                cout << "ALL CONNECTED" << endl;
            }
            else {
                cout << mp.size() << " " << maxsize << endl;
            }

    }
    return 0;
}