併查集是什麼

樹形數據結構

併查集是一種樹形數據結構，用於處理不相交集合（Disjoint Sets）的合併和查詢問題。

併查集中，每個集合可以用一棵樹來表示，其中樹的根節點代表該集合的元素。併查集支持兩種基本操作：合併兩個集合和查詢兩個元素是否屬於同一個集合。通過使用路徑壓縮技術，可以減少查找操作的時間複雜度；通過按秩合併，可以減少合併操作的時間複雜度，從而使併查集的時間複雜度接近常數級別。併查集在計算機科學中有廣泛的套用，如Kruskal算法、Tarjan算法、圖形連通性檢測等。