#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;
//
根據(jù)star的編號(hào)決定誰作為集合的代表，這方便最后根據(jù)集合中最小的索引號(hào)來排序集合
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)) )
//
都一個(gè)集合了，不處理
continue
;
//
相連, 把對(duì)方假如到我的集合中，誰當(dāng)集合代表取決于對(duì)方的集合代表的編號(hào)和我的集合代表的編號(hào)
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;
//
根據(jù)集合代表的編號(hào)大小來排序集合元素，確保了屬于同一個(gè)集合的元素都在連續(xù)空間
//
集合之間按集合代表的編號(hào)排序
qsort(star_idx, K,
sizeof
(
short
), set_id_cmp);
for
( i
=
0
,j
=
1
,k
=
0
;i
<
K
-
1
;i
++
) {
//
i 與 i+1 屬于同一個(gè)集合
if
( ufs_get_root((ufs_elem_t)(stars
+
star_idx[i]))
==
ufs_get_root((ufs_elem_t)(stars
+
star_idx[i
+
1
])) ) {
j
++
;
}
else
{
//
不屬于同一個(gè)集合
//
對(duì)一個(gè)集合的元素排序，根據(jù)元素之間的編號(hào)
qsort(star_idx
+
k, j,
sizeof
(
short
), set_elem_id_cmp);
print_set_elem(k, j);
j
=
1
;
//
新一個(gè)集合的元素個(gè)數(shù)初始化
k
=
i
+
1
;
//
新一個(gè)集合的第一個(gè)元素的位置
}
}
qsort(star_idx
+
k, j,
sizeof
(
short
), set_elem_id_cmp);
print_set_elem(k, j);
return
0
;
}
剛開始以為是圖論的求強(qiáng)連通子圖，后來發(fā)現(xiàn)也沒必要，就是不斷地把符合條件的元素加在一起形成集合，剛好是并查集的經(jīng)典應(yīng)用。
不過題目在輸出順序要求上帶了些難度，所以在并查集的合并過程中做了些改動(dòng)。
這代碼除了并查集，另一個(gè)有趣的地方是怎樣把算法數(shù)據(jù)結(jié)構(gòu)和邏輯數(shù)據(jù)結(jié)構(gòu)結(jié)合起來應(yīng)用，模仿LINUX內(nèi)核的數(shù)據(jù)結(jié)構(gòu)。
更多文章、技術(shù)交流、商務(wù)合作、聯(lián)系博主
微信掃碼或搜索：z360901061
微信掃一掃加我為好友
QQ號(hào)聯(lián)系： 360901061
您的支持是博主寫作最大的動(dòng)力，如果您喜歡我的文章，感覺我的文章對(duì)您有幫助，請(qǐng)用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧，狠狠點(diǎn)擊下面給點(diǎn)支持吧，站長非常感激您！手機(jī)微信長按不能支付解決辦法：請(qǐng)將微信支付二維碼保存到相冊(cè)，切換到微信，然后點(diǎn)擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對(duì)您有幫助就好】元
