题意：有n台电脑，分布在一个二维坐标系中，两台距离不超过d的电脑可以相互通信，初始所有的电脑都是坏的，给出一组操作，第一种操作是修复某台电脑，只有修好的电脑才可以互相通信，第二种操作是询问两台电脑是否可以直接或间接通信。
解法：并查集。将电脑间距离不超过d的两台电脑用无向边连接，当修复一台电脑时就把它和相邻的点合并，查询时只要看是否在一个集里就可以了。
代码：
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<string>
#include<string.h>
#include<math.h>
#include<limits.h>
#include<time.h>
#include<stdlib.h>
#include<map>
#include<queue>
#include<set>
#include<stack>
#include<vector>
#include<iomanip>
#define LL long long
#define lson l, m, rt << 1
#define rson m + 1, r, rt << 1 | 1
using namespace std;
struct node
{
int x, y;
node(int x, int y) : x(x), y(y) {}
node() {}
}point[1005];
vector<int> edge[1005];
int father[1005];
int Find(int a)
{
if(a != father[a]) father[a] = Find(father[a]);
return father[a];
}
void Union(int a, int b)
{
int c = Find(a), d = Find(b);
father[c] = d;
}
int main()
{
int n, d;
scanf("%d%d", &n, &d);
for(int i = 0; i <= n; i++) father[i] = i;
d *= d;
for(int i = 1; i <= n; i++)
{
scanf("%d%d", &point[i].x, &point[i].y);
for(int j = 1; j < i; j++)
{
int tmp = (point[i].x - point[j].x) * (point[i].x - point[j].x) + (point[i].y - point[j].y) * (point[i].y - point[j].y);
if(tmp <= d)
{
edge[i].push_back(j);
edge[j].push_back(i);
}
}
}
char op[5];
int a, b;
bool vis[1005] = {0};
while(~scanf("%s%d", op, &a))
{
if(op[0] == ‘S‘)
{
scanf("%d", &b);
int c = Find(a), d = Find(b);
if(c == d) puts("SUCCESS");
else puts("FAIL");
}
else if(op[0] == ‘O‘)
{
int len = edge[a].size();
vis[a] = true;
for(int i = 0; i < len; i++)
{
if(!vis[edge[a][i]]) continue;
Union(a, edge[a][i]);
}
}
}
return 0;
}
并查集的变量名一直叫abcd的我太蠢了……因为把d写成了b结果debug了一下午……以后坚决不叫abcd了啊啊啊啊啊啊啊啊
原文：http://www.cnblogs.com/Apro/p/4940589.html