併查集
含有「併查集」共 4 篇內容
全部內容
發佈日期由新至舊
今天，我們將用Python list來實現Disjoint Set (併查集，另外也有人稱之為Union-Find)。
Disjoint Set適合用於處理一些子集合的合併和根節點的查找操作。
這種資料結構在圖論中非常有用，特別是在解決連通性相關問題的應用。
Most Stones Removed with Same Row or Column
給定一個2D平面，好幾顆石頭散布在不同的點座標。
輸入陣列代表每顆石頭所在的(x, y)座標。
如果某顆石頭的x座標或者y座標相同的軸線上，還有其他石頭，
則原本那顆石頭可以移除。
請問做多可已移除幾顆石頭?
今天的一魚三吃系列是透過 兩點之間是否存在一條路徑的題目，來回顧以前學過的DFS、BFS和Disjoint Set，鞏固圖論演算法的知識點。
英文的題目敘述在這裡
題目敘述
給定我們已知n個節點的圖，和圖上的每一條無向邊edges。
請問給定的起點start和終點end是否存在一條路徑可
付費限定
題目敘述
題目會給我們一串相鄰矩陣isConnected，相鄰矩陣的元素值isConnected[i][j] 代表第i座城市和第j座城市是否有連通。
如果彼此有連通，則isConnected[i][j]=1。
如果彼此沒有連通，則isConnected[i][j]=0。
彼此互相有路徑可以
