题目链接：点击打开链接
题目大意：给你n个电脑的坐标和一个数字d，这些电脑开始都是损坏的，两个电脑间可以连通如果距离不超过d，而且这种连通性是传递的。再给一些操作：1，检测两个电脑之间是否能连通，并且相应地输出；2，维修好一个电脑
解题思路：显然要用到并查集，可以同一个vector来保存那些已经打开了的电脑，这样就不用遍历所有的电脑了（但其实遍历所有也不会超时），然后判断的时候就搜索一下父亲节点是否相同就行了。
代码：
#include<cstdio> #include<cstdlib> #include<cstring> #include<cmath> #include<iostream> #include<algorithm> #include<string> #include<map> #include<set> #include<vector> #define FAST ios::sync_with_stdio(false) typedef long long ll; const int inf = 0x3f3f3f3f; const int mod = (int)1e9 + 7; const int maxn = (int)1e3 + 5; using namespace std; int pre[maxn]; struct biu{ int x, y, self; } a[maxn]; vector<biu> v; int find(int x){ int r = x; while(pre[r] != r) r = pre[r]; int i = x, t; while(i != r){ t = pre[i]; pre[i] = r; i = t; } return r; } void join(int x, int y){ int fx = find(x), fy = find(y); if(fx != fy) pre[fx] = fy; } ll qpow(ll x, ll y){ ll res = 1; while(y){ if(y & 1) res = (res * x) % mod; y >>= 1; x = (x * x) % mod; } return res; } int main() { int n, d; scanf("%d %d", &n, &d); for(int i = 1; i <= n; i++){ int p, q; scanf("%d %d", &p, &q); a[i].x = p, a[i].y = q; a[i].self = i; pre[i] = i; } char s[5]; while(scanf("%s", s) != EOF){ if(s[0] == 'O'){ int m; scanf("%d", &m); for(int i = 0; i < v.size(); i++){ if(qpow(v[i].x - a[m].x, 2) + qpow(v[i].y - a[m].y, 2) <= d * d){ join(m, v[i].self); } } v.push_back(a[m]); } else{ int m, n; scanf("%d %d", &m, &n); if(find(m) == find(n)) puts("SUCCESS"); else puts("FAIL"); } } return 0; }over