[CF] PrinceOfPersia's blog: Data structures | 程式競賽

sayuan 積分 2

需要的話我可以針對其中一些主題做說明，但請不要說全部 XD

先推薦一下 Disjoint Set1，它的原理跟實作都非常的簡單。基本的用法像是：給一堆 vertex 和 edge，詢問兩個 vertex 之間是否 connected。(若不用 Disjoint Set 的話，就得用 BFS 或 DFS 了)

然後跟 Kruskal's algorithm2(Minimum Spanning Tree) 非常速配。記得以前學到 Kruskal's 的時候還覺得這個演算法相當雞肋，因為沒有容易的方法判斷兩個 vertex 是否屬於同一個 component，後來看到了 Disjoint Set 才驚為天人 :p

http://en.wikipedia.org/wiki/Disjoint-set_data_structure

http://en.wikipedia.org/wiki/Kruskal%27s_algorithm

回應 9 years ago

這是文章的子討論串，你可以回到上層查看所有討論和文章

回上層

Kmark 語法說明

Kmark 是一個類似 Markdown 語法的格式，以下為提供的功能:

種類	語法	呈現
斜體	兩邊加單星	兩邊加單星
粗體	兩邊加雙星	兩邊加雙星
刪除線	~~兩邊加雙曲號~~	~~兩邊加雙曲號~~
引用	> 左邊加個大於符號	左邊加個大於符號
列表	* 可用星號 * 也可以 - 減號 * 數字加點也可以	可用星號也可以 - 減號數字加點也可以
固定寬字	`abcdefghijk` 兩邊用倒引號包住	`abcdefghijk`
編碼區塊	``` function abc() ``` 上下都用三個倒引號包住	`function abc()`
連結	[這是連結][1] [1]: http://example.com 連結第一部份是文字，先用中括號包住，後面再加上 [編號]。第二部份是連結本身，放在文末，開頭是 [編號]: http	這是連結1 1 http://example.com

Kmark 語法說明

Kmark 是一個類似 Markdown 語法的格式，以下為提供的功能:

種類	語法	呈現
斜體	兩邊加單星	兩邊加單星
粗體	兩邊加雙星	兩邊加雙星
刪除線	~~兩邊加雙曲號~~	~~兩邊加雙曲號~~
引用	> 左邊加個大於符號	左邊加個大於符號
列表	* 可用星號 * 也可以 - 減號 * 數字加點也可以	可用星號也可以 - 減號數字加點也可以
固定寬字	`abcdefghijk` 兩邊用倒引號包住	`abcdefghijk`
編碼區塊	``` function abc() ``` 上下都用三個倒引號包住	`function abc()`
連結	[這是連結][1] [1]: http://example.com 連結第一部份是文字，先用中括號包住，後面再加上 [編號]。第二部份是連結本身，放在文末，開頭是 [編號]: http	這是連結1 1 http://example.com