Wireless Network POJ - 2236

Sample Input

4 1
0 1
0 2
0 3
0 4
O 1
O 2
O 4
S 1 4
O 3
S 1 4

Sample Output

FAIL

SUCCESS

思路：题目说电脑是坏的，所以你要先把所有电脑都当做一个树但是不能动，如果电脑被修复了，这个树才可以被拿出来用，一道并查集的题加上一个距离计算.

#include <stdio.h> #include <string.h> char str[10]; int n; int d; int vis[1005]; int parent[1005]; int x[1005]; int y[1005]; int find(int x) {     if(parent[x]==x) return x;     else     return find(parent[x]); } void unite(int x, int y) {     x=find(x);     y=find(y);     parent[x]=y; } int distance (int a,int b, int c, int e) {     if((a-c)*(a-c)+(b-e)*(b-e)<=d*d)    return 1;     else    return 0; } void init() {     memset(vis,0,sizeof(vis));     scanf("%d%d",&n,&d);     for(int i=1;i<=n;i++)         parent[i]=i; } int main(void) {     init();     for(int i=1;i<=n;i++)         scanf("%d%d",&x[i],&y[i]);     while((scanf("%s",str))==1)     {     if(str[0]=='O')     {         int num;         scanf("%d",&num);         vis[num]=1;         for(int i=1;i<=n;i++)         {             if( vis[i]==1 && distance(x[i],y[i],x[num],y[num]) == 1 )             {                 unite(i,num);                 //printf("%d=%d\n",num,parent[num]);             }         }     }     if(str[0]=='S')     {         int num1,num2;         scanf("%d%d",&num1,&num2);         if(find(num1)==find(num2))         printf("SUCCESS\n");         else         printf("FAIL\n");     }     }     return 0; }

这题用路径压缩可以减少了900MS