首页 > 代码库 > poj 2236 Wireless Network 并查集

poj 2236 Wireless Network 并查集

#include <stdio.h>#include <string.h>#include <math.h>#define maxn 1220double x[maxn],y[maxn],d;bool vis[maxn];int p[maxn];int n;double dist(int i,int j){    return fabs( (x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]) );}int find(int x){    if(x==p[x]) return p[x];    return p[x]=find(p[x]);}void link(int a,int b){    int fa=find(a);    int fb=find(b);    if(fa!=fb)        p[fa]=fb;}int main(){    int i;    int u,v;    scanf("%d%lf",&n,&d);    for(i=1;i<=n;i++)    {        scanf("%lf%lf",&x[i],&y[i]);        p[i]=i;        vis[i]=0;    }    char op;    getchar();    while(scanf("%c",&op)!=EOF)    {        if(op==O)        {            scanf("%d",&u);            vis[u]=1;            for(i=1;i<=n;i++)                if(vis[i]&&i!=u&&dist(i,u)<=d*d)                    link(i,u);        }        else        {            scanf("%d%d",&u,&v);            int fu=find(u);            int fv=find(v);            if(fu!=fv) printf("FAIL\n");            else printf("SUCCESS\n");        }        getchar();    }    return 0;}