java并查集计算机网络连通,poj2236 Wireless Network（并查集）

题意：有n台损坏的电脑，现要将其逐台修复，且使其相互恢复通信功能。若两台电脑能相互通信，则有两种情况，一是他们之间的距离小于d，二是他们可以借助都可到达的第三台已修复的电脑。给出所有电脑的坐标位置，对其进行两种可能的操作，O

x表示修复第x台，S x y表示判断x y之间能否通信，若能输出SUCCESS，否则输出FALL。

思路：判断图的连通性问题，可以借助并查集。首先，电脑之间若能通信，则大前提就是两台电脑都是维修过的，因此处理联通问题时，必须在已修好的电脑中进行。由于通信可以传递，因此只要满足能够通信的条件，则新加入的电脑就可以借助这个小网络与其中任意一台通信，这就是使用并查集的关键条件，因此，将满足距离关系的电脑并入一个集合中，此后每加入一台电脑都与前面加入的所有电脑做一次联通性的判断，即只要距离小于d就并入集合即可。

Accepted 144K 1141MS

#include

#include

#define MAXN 1010

int n, rank[MAXN], father[MAXN], repaired[MAXN];

struct Pos {

int x,

y;

} pos[MAXN];

void make_set()

{

for (int i =

1; i <= n; ++i)

rank[i] = 0, father[i] = i;

}

int find_set(int x)

{

if (x !=

father[x])

father[x] = find_set(father[x]);

return

father[x];

}

void union_set(int x, int y)

{

x =

find_set(father[x]);

y =

find_set(father[y]); // 多向上找一层

if (x !=

y)

{

if (rank[x] < rank[y])

father[x] = y;

else

{

father[y] = x;

if (rank[x] == rank[y])

++rank[x];

}

}

}

double distance(int a, int b) // 注意标号转换一下

{

Pos x,

y;

x =

pos[a];

y =

pos[b];

return

sqrt(1.0*(x.x-y.x)*(x.x-y.x) + 1.0*(x.y-y.y)*(x.y-y.y));

}

int main()

{

char

c;

int i, x, y,

cnt;

double

d;

scanf("%d%lf", &n, &d);

for (i = 1;

i <= n; ++i) // 编号1到n..

scanf("%d%d", &pos[i].x,

&pos[i].y);

cnt =

0;

make_set();

while

(scanf(" %c%d", &c, &x) !=

EOF)

if (c == 'O')

{

for (i = 0; i

< cnt; ++i) // 与已修好的电脑合并

if

(distance(repaired[i], x) <= d)

union_set(repaired[i],

x);

repaired[cnt++]

= x; // 加入修好的集合中，逻辑其实恰好相反，是先修再合并

}

else

{

scanf("%d", &y);

if

(find_set(x) == find_set(y)) // 判断连通性

printf("SUCCESS\n");

else

printf("FAIL\n");

}

return

0;

}

总结

以上是生活随笔为你收集整理的java并查集计算机网络连通,poj2236 Wireless Network（并查集）的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。