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;
}
本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！