simplicity is prerequisite for reliability

背景

數據結構是計算機科學的基礎學科,其中許多簡單的數據結構早已被各種高級語言抽象成類庫,以方便人們使用,如數組、列表、優先隊列、哈希表等等。

我習慣於把那些比較難以抽象成通用組件的數據結構,稱爲「高級數據結構」。這些數據結構通常只適用於解決某幾類問題,在使用過程中還需要針對問題模型作出一些定製性的優化,如果硬要抽象成通用組建反而限制了它們的性能。

并查集夠高效地判斷兩個元素是否同屬一個集合、合併兩個集合,常用與解決一些不相交集合的合併和查詢問題,比如計算無向圖的聯通分量個數、染色,在 CodeForces 中,并查集的標籤是 dsu,因爲并查集的英文是 Disjoint Set Union,「并查集」這個翻譯可能更多的來自一個英文別稱 Merge–Find Set 。

Read More...