题目链接

Wireless Network POJ - 2236

思路

$$ \begin{aligned}并查集基础题。\end{aligned} $$

时间复杂度

$$ O(N^2 \alpha (N)) $$

代码

#include <cstdio>
#include <vector>

using namespace std;


class DSU {
public:
    vector<int> p, r;

    void init(int n) {
        p.resize(n + 10);
        r.resize(n + 10);
        for (int i = 0; i <= n; i++) {
            p[i] = i;
            r[i] = 0;
        }
    }

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

    bool unite(int x, int y) {
        x = find(x);
        y = find(y);
        if (x == y) {
            return false;
        }

        if (r[x] < r[y]) {
            p[x] = y;
        } else {
            p[y] = x;
            if (r[x] == r[y]) {
                r[x]++;
            }
        }
        return true;
    }

    bool same(int x, int y) {
        return find(x) == find(y);
    }
};

const int MAXN = 1e3 + 10;

int n, d;
int x[MAXN], y[MAXN];
bool ok[MAXN];

bool check(int a, int b) {
    if ((x[a] - x[b]) * (x[a] - x[b]) 
      + (y[a] - y[b]) * (y[a] - y[b]) 
      <= d * d) {
        return true;
    } else {
        return false;
    }
}

int main() {
    scanf("%d%d", &n, &d);// don't forget &
    DSU dsu;
    dsu.init(n);
    for (int i = 1; i <= n; i++) {
        scanf("%d%d", &x[i], &y[i]);// don't forget &
    }
    char op[5];
    while (~scanf("%s", op)) {
        if (op[0] == 'O') {
            int a;
            scanf("%d", &a);// don't forget &
            ok[a] = true;
            for (int i = 1; i <= n; i++) {
                if (ok[i] && check(i, a)) {
                    dsu.unite(i, a);
                }
            }
        } else {
            int a, b;
            scanf("%d%d", &a, &b);// don't forget &
            printf("%s\n", dsu.same(a, b) ? "SUCCESS" : "FAIL");
        }
    }

    return 0;
}