並查集的路徑壓縮：並查集優化，讓查找更快
並查集用於解決集合合併與元素歸屬問題（如連通性判斷）。核心操作是`find`（查找根節點）和`union`（合併集合），基礎版通過`parent`數組記錄父節點實現，但長鏈結構會導致`find`效率極低。爲優化，引入**路徑壓縮**：在`find`過程中，將路徑上所有節點直接指向根節點，使樹結構扁平化，查找效率接近O(1)。路徑壓縮通過遞歸或迭代實現，將長鏈轉化爲“一步到位”的短路徑。結合按秩合併等優化，可高效處理大規模集合問題，成爲解決連通性、歸屬判斷的核心工具。
閱讀全文並查集：並查集是什麼？解決“朋友關係”問題的方法
並查集是管理元素分組的高效數據結構，核心解決“合併組”（Union）和“查詢是否同組”（Find）問題，適用於快速判斷元素是否屬於同一集合的場景。其底層以parent數組維護父節點關係，每組視爲一棵樹，根節點爲組代表，初始各元素自成一組。 關鍵優化是**路徑壓縮**（查詢時壓縮路徑，使節點直接指向根）和**按秩合併**（小樹依附大樹，避免樹退化爲鏈表），確保操作接近常數時間複雜度。核心方法`find`（查找根節點並壓縮路徑）和`union`（合併兩組，小樹根指向大樹根）實現高效分組。 應用廣泛，如網絡連接判斷、家族關係查詢、最小生成樹（Kruskal算法）及等價類問題等，是處理分組場景的簡潔強大工具。
閱讀全文