算法特别篇_并查集思路
概：近一個月leetcode出了一個月的并查集每日一題，有人驚呼：“這個月不學會并查集誰也别想走”，于是在通過找一些資料學習，并錘煉一些每日一題後，我有了自己的感悟，決定記下來。本篇主要講述并查集抽象思維和案例（LeetCode_778_水位上升的泳池中遊泳）的做法。
來源：力扣（LeetCode）
連結：LeetCode_778_水位上升的泳池中遊泳
并查集抽象思路
- 聲明：由于我在算法方面也是個菜雞的緣故，遂一下内容可能會有不妥之處，還望大佬指正。
- 并查集有什麼用：你可以看成一張圖，圖中有很多個節點，然後你需要讓某倆個節點可以“連通”（即一個點可以通過其他若幹個點到達另一個點）起來，這時候可能就用的到并查集了。再或者說，有一堆資料，你需要為其歸類，存在某種聯系的資料歸為一類，這種聯系題中給你了，你需要把一對有這種聯系的資料歸到一起，a與b一類，b與c一類，并查集會把a和c自動歸到一起，是以你隻需要向前看，把題中給好的直接倆倆關系湊到一起，不需要管間接關系的問題（這一手叫做沒有後顧之憂）。
- 并查集怎麼用：
- 并查集的形象上來說其實類似樹結構，a節點和b節點要相連，就把a作為b的父節點或者b作為a的父節點。
- 假設有這麼一種情況，b為a的父節點，d為c的父節點，如下圖： 這時候題中的條件給你說a和c是要連上的，如果你把a和c直接相連，會形成這種情況：
算法特别篇_并查集思路(LeetCode_778_水位上升的泳池中遊泳) a的根節點是b，c的根節點是d，之後讀取這個結構怎麼判斷a和c是否連接配接上了呢，（如果你很老實的給每個節點很大一塊空間，存了其所有的連接配接節點，那就是正常的構圖了，不屬于并查集範疇），是以如果這時候我們是讓a的父節點歸于c的父節點之下，即b成為d的子節點如下圖：
算法特别篇_并查集思路(LeetCode_778_水位上升的泳池中遊泳) 這時候就可以通過同一個根節點來判斷，a和c是連通的。 算法特别篇_并查集思路(LeetCode_778_水位上升的泳池中遊泳)
- 并查集類實作的核心：
- 有一個parents集合，來表示點與點之間的關系，可以是數組，parents[i]表示資料i的父節點的值。也可以是map直接映射倆個點的資料。
- 構造方法，主要任務是實作空間的開拓和初始化，如果你用map動态來的話當我沒說，如果是數組，那麼每個點最開始都要設定好預設的值，預設沒有父節點，那麼父節點設定為自己本身，檢索的時候就會檢查到目前點為根節點。
- Find方法，用來查詢某個值的根節點是誰，如果parents[i]==i，那麼說明目前節點自身就是根節點了（其沒有父節點），否則其根節點就是其父節點的根節點，也就是Find(parents[i]);
- marge方法，我叫其為合并，主要用來實作将倆個有聯系的節點連接配接到一起，當然，說的不是直接連起來，而是歸為同一跟下，就是上面圖說的将某一節點的根歸到另一個節點的根下面。是以這個方法首先判斷其是否為同一根下，如果是，則結束，如果不是，則讓其中一個點的根歸到另一個節點的根下。
- 大概要實作的核心如上，根據題目的要求，在做一些簡單邏輯上的修改，拿到自己需要的資料即可。
- 做并查集需要抽象出的資訊：
- 節點本身是什麼
- 節點間的關系是什麼
- 如何周遊節點間的關系，讓其連接配接起來
- 最後需要得到的資料是什麼
題目
在一個 N x N 的坐标方格 grid 中，每一個方格的值 grid[i][j] 表示在位置 (i,j) 的平台高度。
現在開始下雨了。當時間為 t 時，此時雨水導緻水池中任意位置的水位為 t 。你可以從一個平台遊向四周相鄰的任意一個平台，但是前提是此時水位必須同時淹沒這兩個平台。假定你可以瞬間移動無限距離，也就是預設在方格内部遊動是不耗時的。當然，在你遊泳的時候你必須待在坐标方格裡面。
你從坐标方格的左上平台 (0，0) 出發。最少耗時多久你才能到達坐标方格的右下平台 (N-1, N-1)？
示例
示例 1:
輸入: [[0,2],[1,3]]
輸出: 3
解釋:
時間為0時，你位于坐标方格的位置為 (0, 0)。
此時你不能遊向任意方向，因為四個相鄰方向平台的高度都大于目前時間為 0 時的水位。
等時間到達 3 時，你才可以遊向平台 (1, 1). 因為此時的水位是 3，坐标方格中的平台沒有比水位 3 更高的，是以你可以遊向坐标方格中的任意位置
示例2:
輸入: [[0,1,2,3,4],[24,23,22,21,5],[12,13,14,15,16],[11,17,18,19,20],[10,9,8,7,6]]
輸出: 16
解釋:
0 1 2 3 4
24 23 22 21 5
12 13 14 15 16
11 17 18 19 20
10 9 8 7 6
最終的路線用加粗進行了标記。
我們必須等到時間為 16，此時才能保證平台 (0, 0) 和 (4, 4) 是連通的
提示
1）2 <= N <= 50.
2）grid[i][j] 是 [0, …, N*N - 1] 的排列。
思路
- 首先讀完題知道題目要做什麼：水位達到某一高度後，你可以從左上角點位遊到最下角點位，求這個最低高度。
- 然後去抽象并查集四大資訊：1. 節點本身就是它的坐标(x,y)，而通過提示我們可以知道，x和y不會超過50，那麼我們可以将x和y壓縮到一個int資料中，既有：x*每行個數+y。得到的int資料是唯一且連續的，我們可以用其作為節點本身的參照。2. 節點間的關系是四面相鄰，從一個點出發，隻能直接到達其相鄰點位，并且當水位高過目前點位的時候，你才能從目前點位出發，然後遊到相鄰的四個點位中比目前水位低的點。3. 如何周遊，由于題目中說了是要求最低水位，是以我們以水位上升作為變量來一步步去連接配接節點。當水位升到某一高度後，等于該高度的平台就可以和四周更低高度的平台相連，調用marge方法。4. 要得到的值是允許左上角點與右下角點連通的最低水位值，是以當某一次水位上升合并完平台之後，我們檢查目前左上角與右下角點位是否連通，若連通直接傳回目前水位即可。
c++完整代碼
class Unionfind
{
public:
vector<int> parents;
Unionfind(int n)
{
for (int i = 0; i < n; i++)
{
parents.push_back(i);
}
}
int Find(int x)
{
if (parents[x] == x) return x;
else return Find(parents[x]);
}
void marge(int x,int y)
{
if (Find(x) != Find(y))
{
parents[Find(x)] = Find(y);
}
}
bool rt()
{
if (Find(0) == Find(parents.size() - 1)) return true;
else return false;
}
};
class Solution {
public:
map<int, vector<int>> ma;
int swimInWater(vector<vector<int>>& heights) {
for (int i = 0; i < heights.size(); i++)
for (int j = 0; j < heights[0].size(); j++)
{
insert(i* heights[0].size() + j, heights[i][j]);
}
Unionfind uf(heights.size() * heights[0].size());
map<int, vector<int>>::iterator it = ma.begin();
for (int i = 0; i < ma.size(); i++)
{
vector<int>& ve = it->second;
for (int j = 0; j < ve.size(); j ++)
{
int x = ve[j]/heights[0].size();
int y = ve[j]%heights[0].size();
if(x-1>=0&&heights[x-1][y]<=heights[x][y])
uf.marge(ve[j],ve[j]-heights[0].size());
if(x+1<heights.size()&&heights[x+1][y]<=heights[x][y])
uf.marge(ve[j],ve[j]+heights[0].size());
if(y-1>=0&&heights[x][y-1]<=heights[x][y])
uf.marge(ve[j],ve[j]-1);
if(y+1<heights[0].size()&&heights[x][y+1]<=heights[x][y])
uf.marge(ve[j],ve[j]+1);
}
if (uf.rt()) return it->first;
it++;
}
return 0;
}
void insert(int x, int h)
{
if (ma.count(h) == 0) ma.insert(pair<int, vector<int>>(h, vector<int>()));
ma.find(h)->second.push_back(x);
}
};