Wireless Network（并查集）

 1 #include<iostream> 2 #include<algorithm> ?3 #include<cstring> 4 #include<cmath> 5 using namespace std; 6 ?7 int n,d; 8 char c; 9 int p,q;10 int book[1005]={0},f[1005]; //分别是 标记是否修好 ， 找爸 11 12 struct note13 {14 ????int x,y;15 }a[1005]; //记录坐标 16 17 int getf(int u)18 {19 ????return u==f[u]? u:getf(f[u]);20 }21 22 void merge(int x,int y)23 {24 ????x=getf(x);25 ????y=getf(y);26 ????if(x!=y)27 ????{28 ????????f[y]=x;29 ????}30 }31 32 int main()33 {34 ????cin>>n>>d;35 ????for(int i=1;i<=n;i++)36 ????{37 ????????f[i]=i;38 ????????cin>>a[i].x>>a[i].y;39 ????}40 ????while(cin>>c)41 ????{42 ????????if(c==‘O‘) //修 43 ????????{44 ????????????cin>>p;45 ????????????book[p]=1; ?//修好了 ,下面进行寻找 46 ????????????for(int i=1;i<=n;i++)47 ????????????{ 48 ????????????????//第i个电脑不和第p的电脑超出距离，并且第i个电脑已经被修好 是能连通的基本条件 49 ????????????????if( d*d >= 1.0*((a[p].x-a[i].x)*(a[p].x-a[i].x)+(a[p].y-a[i].y)*(a[p].y-a[i].y)) && book[i]==1) 50 ????????????????????merge(f[p],f[i]); //这里左右位置不要变，要一直都把电脑p作为爸爸 51 ????????????}52 ????????}53 ????????else if(c==‘S‘)54 ????????{55 ????????????cin>>p>>q;56 ????????????if(getf(p)==getf(q))57 ????????????????cout<<"SUCCESS"<<endl;58 ????????????else59 ????????????????cout<<"FAIL"<<endl;60 ????????}61 ????}62 }