發表新討論
#4378: 解题小提示


liouzhou_101 (王启圣)

學校 : 广西柳州高级中学
編號 : 3714
來源 : [126.108.190.144]
最後登入時間 ：
2023-07-21 17:40:51
d808. 黑暗部落 | From: [180.137.71.24] | 發表日期 : 2010-10-10 17:02

这题可以用  并查集(disjoint set)  或者是  用链表(指针)来存边+DFS查找  。

时间复杂度都是 O(n) 的，但是后者较慢，编程复杂度高，程序(程式)长。//后者较慢是什么原因呢？我还不是很清楚

另外，若选择后者，链表(指针)不要dispose(free)，这样会TLE.

 
#4383: Re:解题小提示


leopan0922 (zz)

學校 : 臺北市立成功高級中學
編號 : 6612
來源 : [140.113.225.106]
最後登入時間 ：
2016-08-15 15:44:07
d808. 黑暗部落 | From: [219.70.171.51] | 發表日期 : 2010-10-10 19:48

这题可以用  并查集(disjoint set)  或者是  用链表(指针)来存边+DFS查找  。

时间复杂度都是 O(n) 的，但是后者较慢，编程复杂度高，程序(程式)长。//后者较慢是什么原因呢？我还不是很清楚

另外，若选择后者，链表(指针)不要dispose(free)，这样会TLE.


感謝你的提示

我又學會新的一招了^^

 
ZeroJudge Forum