#include
<
iostream
>
using
namespace
std;
typedef
struct
ufs_elem_st {
struct
ufs_elem_st
*
next,
*
prev;
struct
ufs_elem_st
*
parent;
} ufs_elem_st,
*
ufs_elem_t;
typedef
struct
ufs_st {
ufs_elem_st
*
roots;
} ufs_st,
*
ufs_t;
typedef
struct
star_st {
ufs_elem_st ufs_elem;
int
x,y,z,r;
} star_st,
*
star_t;
int
K;
short
star_idx[
1001
]
=
{
0
};
star_st stars[
1001
]
=
{
0
};
ufs_elem_t ufs_get_root(ufs_elem_t me) {
ufs_elem_t my_root
=
me;
while
( my_root
->
parent
!=
my_root
&&
my_root
->
parent
!=
NULL )
my_root
=
my_root
->
parent;
me
->
parent
=
my_root;
//
路径压缩
return
my_root;
}
void
ufs_add_root(ufs_t ufs, ufs_elem_t me) {
ufs_elem_t my_root
=
ufs_get_root(me);
if
( NULL
!=
ufs
->
roots ) {
my_root
->
next
=
ufs
->
roots;
ufs
->
roots
->
prev
=
my_root;
}
ufs
->
roots
=
my_root;
my_root
->
prev
=
NULL;
}
void
ufs_join(ufs_t ufs, ufs_elem_t friend_elem, ufs_elem_t me) {
ufs_elem_t my_root
=
ufs_get_root(me);
ufs_elem_t friend_root
=
ufs_get_root(friend_elem);
ufs_elem_t final_root
=
NULL;
if
( NULL
!=
my_root
->
next )
my_root
->
next
->
prev
=
my_root
->
prev;
if
( NULL
!=
my_root
->
prev )
my_root
->
prev
->
next
=
my_root
->
next;
if
( ufs
->
roots
==
my_root )
ufs
->
roots
=
my_root
->
next;
my_root
->
next
=
my_root
->
prev
=
NULL;
if
( NULL
!=
friend_root
->
next )
friend_root
->
next
->
prev
=
friend_root
->
prev;
if
( NULL
!=
friend_root
->
prev )
friend_root
->
prev
->
next
=
friend_root
->
next;
if
( ufs
->
roots
==
friend_root )
ufs
->
roots
=
friend_root
->
next;
friend_root
->
next
=
friend_root
->
prev
=
NULL;
//
合并集合
star_t s1
=
(star_t)my_root, s2
=
(star_t)friend_root;
//
根据star的编号决定谁作为集合的代表，这方便最后根据集合中最小的索引号来排序集合
if
( s1
-
stars
<
s2
-
stars ) {
friend_root
->
parent
=
my_root;
final_root
=
my_root;
}
else
{
my_root
->
parent
=
friend_root;
final_root
=
friend_root;
}
if
( NULL
!=
ufs
->
roots ) {
final_root
->
next
=
ufs
->
roots;
ufs
->
roots
->
prev
=
final_root;
}
ufs
->
roots
=
final_root;
}
bool
check(star_t s1, star_t s2) {
int
distSquare
=
(s1
->
x
-
s2
->
x)
*
(s1
->
x
-
s2
->
x)
+
(s1
->
y
-
s2
->
y)
*
(s1
->
y
-
s2
->
y)
+
(s1
->
z
-
s2
->
z)
*
(s1
->
z
-
s2
->
z);
int
r1r2Square
=
(s1
->
r
+
s2
->
r)
*
(s1
->
r
+
s2
->
r);
if
( distSquare
<
r1r2Square )
return
true
;
else
return
false
;
}
int
set_id_cmp(
const
void
*
i1,
const
void
*
i2) {
ufs_elem_t e1
=
(ufs_elem_t)(stars
+
*
(
short
*
)i1);
ufs_elem_t e2
=
(ufs_elem_t)(stars
+
*
(
short
*
)i2);
return
ufs_get_root(e1)
-
ufs_get_root(e2);
}
int
set_elem_id_cmp(
const
void
*
i1,
const
void
*
i2) {
return
*
(
short
*
)i1
-
*
(
short
*
)i2;
}
void
print_set_elem(
int
start,
int
len) {
int
i;
len
--
;
for
(i
=
0
;i
<
len;i
++
)
cout
<<
star_idx[start
+
i]
<<
"
,
"
;
cout
<<
star_idx[start
+
i]
<<
endl;
}
int
main() {
int
i,j,k;
bool
find_grp;
ufs_st ufs
=
{
0
};
cin
>>
K;
for
( i
=
0
;i
<
K;i
++
)
cin
>>
stars[i].x
>>
stars[i].y
>>
stars[i].z
>>
stars[i].r;
for
( i
=
0
;i
<
K;i
++
) {
for
( j
=
i
+
1
;j
<
K;j
++
) {
if
( ufs_get_root((ufs_elem_t)(stars
+
i))
==
ufs_get_root((ufs_elem_t)(stars
+
j)) )
//
都一个集合了，不处理
continue
;
//
相连, 把对方假如到我的集合中，谁当集合代表取决于对方的集合代表的编号和我的集合代表的编号
if
( check(stars
+
i, stars
+
j)
==
true
)
ufs_join(
&
ufs, (ufs_elem_t)(stars
+
i), (ufs_elem_t)(stars
+
j));
}
}
for
( i
=
0
;i
<
K;i
++
)
star_idx[i]
=
i;
//
根据集合代表的编号大小来排序集合元素，确保了属于同一个集合的元素都在连续空间
//
集合之间按集合代表的编号排序
qsort(star_idx, K,
sizeof
(
short
), set_id_cmp);
for
( i
=
0
,j
=
1
,k
=
0
;i
<
K
-
1
;i
++
) {
//
i 与 i+1 属于同一个集合
if
( ufs_get_root((ufs_elem_t)(stars
+
star_idx[i]))
==
ufs_get_root((ufs_elem_t)(stars
+
star_idx[i
+
1
])) ) {
j
++
;
}
else
{
//
不属于同一个集合
//
对一个集合的元素排序，根据元素之间的编号
qsort(star_idx
+
k, j,
sizeof
(
short
), set_elem_id_cmp);
print_set_elem(k, j);
j
=
1
;
//
新一个集合的元素个数初始化
k
=
i
+
1
;
//
新一个集合的第一个元素的位置
}
}
qsort(star_idx
+
k, j,
sizeof
(
short
), set_elem_id_cmp);
print_set_elem(k, j);
return
0
;
}
刚开始以为是图论的求强连通子图，后来发现也没必要，就是不断地把符合条件的元素加在一起形成集合，刚好是并查集的经典应用。
不过题目在输出顺序要求上带了些难度，所以在并查集的合并过程中做了些改动。
这代码除了并查集，另一个有趣的地方是怎样把算法数据结构和逻辑数据结构结合起来应用，模仿LINUX内核的数据结构。
