思路详见课本 P 213

思路：直接用并查集，最后看 p 和 q 是否 在一个 集合中 即可。属于同一集合，则 可以通信；否则失败。

#include<iostream>#include<cstring>using namespace std;const int maxn=1000 +100;int set[maxn];int xx[maxn];int yy[maxn];bool valid[maxn];int n,d;int set_find(int d)//路径压缩的 合并树根 的函数{	if(set[d]<0)		return d;	return set[d]=set_find(set[d]);}void join(int x,int y){	x=set_find(x);	y=set_find(y);	if(x!=y)//-----------此处这个判断千万不能少，否则在 set_find()函数中，出现死循环（由于节点 自己 指向 自己，找不到 结束条件 （即树根））		//------------提交会出现runtime error  		set[x]=y;}int in(int i,int p)//判断i 是否在 p的范围内{	if(  (xx[i]-xx[p]) * (xx[i]-xx[p]) + (yy[i]-yy[p]) * (yy[i]-yy[p]) <= d*d  )		return 1;	return 0;}void repair(int p)//修复 p{	valid[p]=1;	int i;	for(i=1;i<=n;i++) 		if( valid[i] &&in(i,p) &&i!=p)			join(i,p);}void search(int p,int q) //查看 p  和 q是否 可以 通信{	if( set_find(p)==set_find(q) )		cout<<"SUCCESS"<<endl;	else		cout<<"FAIL"<<endl;}int main(){	memset(set,-1,sizeof(set));	memset(xx,0,sizeof(xx));	memset(yy,0,sizeof(yy));	memset(valid,0,sizeof(valid));	cin>>n>>d;	int i;	for(i=1;i<=n;i++)		cin>>xx[i]>>yy[i];	char c;	while(cin>>c)	{		if(c==‘O‘)		{			int p;			cin>>p;			repair(p);		}		else if(c==‘S‘)		{			int p,q;			cin>>p>>q;			search(p,q);		}	}	return 0;}