POJ 2236 Wireless Network（并查集）

链接：http://poj.org/problem?id=2236

解题思路：首先通过并查集划分集合，根据每个点(每对计算机)的从属关系来判断点（计算机）是否连通；

需根据计算机的通信范围确定每对计算机是否可以进行直接通信；

必须保证可以进行通信的每对计算机都是完好无损的（即已经经过维修的）；

1. 输入每个计算机的坐标后，判断哪些点可以直接通信，记录；

2. 当输入的操作是维修时，标记当前计算机已经过维修，并将其与所有的完好的可以直接进行通信的计算机进行结合；

3. 当输入的操作是询问时，如果两台计算机有相同的根节点，则表示，可通信，否则不行；

代码如下：

#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <cstdlib>
#define MAXN 1005
#define RST(N)memset(N, 0, sizeof(N))
using namespace std;

int father[MAXN], n, map[MAXN][MAXN];
double m;
int flag[MAXN], x[MAXN], y[MAXN], Mc, Md;
char command[20];

void Init()
{
    for(int i=1; i<=n; i++) scanf("%d %d", &x[i], &y[i]);
    for(int i=1; i<=n; i++) father[i] = i;
    RST(flag), RST(map);
}

int Find(int x)
{
    if(x != father[x]) {
        father[x] = Find(father[x]);
    }
    return father[x];
}

void Union(int x, int y)
{
    x = Find(x), y = Find(y);
    if(x == y) return ;
    father[x] = y;
}

double Mul(int x) { return x*x; }
bool check(int x, int y) { return Find(x) == Find(y); }

int main()
{
    while(~scanf("%d %lf", &n, &m)) {
        Init();
        for(int i=1; i<=n-1; i++) {
            for(int j=i+1; j<=n; j++) {
                double M = sqrt((double)Mul(x[i]-x[j])+Mul(y[i]-y[j]));
                if(M <= m) { map[i][j] = 1, map[j][i] = 1; }
            }
        }
        while(~scanf("%s", command)) {
            if(strcmp(command, "O") == 0) {
                scanf("%d", &Md);
                flag[Md] = 1;
                for(int i=1; i<=n; i++) {
                    if(map[i][Md] && flag[i]) Union(Md, i);
                }
            }else if(strcmp(command, "S") == 0) {
                scanf("%d %d", &Mc, &Md);
                if(check(Mc, Md)) puts("SUCCESS");
                else puts("FAIL");
            }
        }
    }
    return 0;
}

POJ 2236 Wireless Network（并查集）,古老的榕树,5-wow.com