數據結構與算法：圖論—

先給出并查集的模板，還有一些leetcode算法題，以后遇見了相關題目再往上增加

并查集模板

整體模板C++代碼如下：

空間復雜度： O(n) ，申請一個father數組。
時間復雜度

路徑壓縮后的并查集時間復雜度在O(logn)與O(1)之間，且隨著查詢或者合并操作的增加，時間復雜度會越來越趨于O(1)。

int n = 51000;
vector<int> father = vector<int>(n);
/*
錯誤的方法
class Foo(){
private:vector<string> name(5); //error in these 2 linesvector<int> val(5,0);
}
正確的方法
C++11以后：
class Foo(){
private:vector<string> name = vector<string>(5);vector<int> val{vector<int>(5,0)};
}
*/// 并查集初始化
void init() {for (int i = 0; i < father.size(); i++) {father[i] = i;}
}// 并查集里尋根的過程：路徑壓縮
int find(int a) {if (father[a] == a)return a;elsereturn father[a] = find(father[a]);
}bool same(int a, int b) {a = find(a);b = find(b);return a == b;
}// 將a->b 這條邊加入并查集
void join(int a, int b) {a = find(a);    //找根b = find(b);if (a == b)return;elsefather[a] = b;
}init();

1、1971. 尋找圖中是否存在路徑

思路：直接并查集套用即可

提示：

1 <= n <= 2 * 105
0 <= edges.length <= 2 * 105
edges[i].length == 2
0 <= ui, vi <= n - 1
ui != vi
0 <= source, destination <= n - 1
不存在重復邊
不存在指向頂點自身的邊

class Solution {
public:int n = 200001;vector<int> father = vector<int>(n);void init() {for (int i = 0; i < n; i++) {father[i] = i;}}int find(int a) {if (a == father[a])return a;else {return father[a] = find(father[a]);}}void join(int a, int b) {a = find(a);b = find(b);if (a == b)return;else {father[a] = b;}}bool validPath(int n, vector<vector<int>>& edges, int source,int destination) {init();for (auto& a : edges) {join(a[0], a[1]);}return find(source) == find(destination);}
};
image-20240509155416437

2、547. 省份數量

思路：并查集：再通過set來統計個數

有 n 個城市，其中一些彼此相連，另一些沒有相連。如果城市 a 與城市 b 直接相連，且城市 b 與城市 c
直接相連，那么城市 a 與城市 c 間接相連。

省份是一組直接或間接相連的城市，組內不含其他沒有相連的城市。

給你一個 n x n 的矩陣 isConnected ，其中 isConnected[i][j] = 1 表示第 i
個城市和第 j 個城市直接相連，而 isConnected[i][j] = 0 表示二者不直接相連。

返回矩陣中省份的數量。

示例 1：

輸入：isConnected = [[1,1,0],[1,1,0],[0,0,1]] 輸出：2

示例 2：

輸入：isConnected = [[1,0,0],[0,1,0],[0,0,1]] 輸出：3

提示：

1 <= n <= 200
n == isConnected.length
n == isConnected[i].length
isConnected[i][j] 為 1 或 0
isConnected[i][i] == 1
isConnected[i][j] == isConnected[j][i]

class Solution {
public:int n = 205;vector<int> father{vector<int>(n)};void init() {for (int i = 0; i < n; i++) {father[i] = i;}}int find(int a) {if (a == father[a])return a;else {return father[a] = find(father[a]);}}void join(int a, int b) {a = find(a);b = find(b);if (a == b)return;else {father[a] = b;}}int findCircleNum(vector<vector<int>>& isConnected) {init();int len = isConnected.size();for (int i = 0; i < len; i++) {for (int j = 0; j < len; j++) {if (isConnected[i][j]) {join(i, j);}}}// 統計父節點的個數有兩種方式：// 1、使用set比較直觀：但是復雜度高// unordered_set<int> st;// for (int i = 0; i < len; i++) {//     st.insert(find(i));// }// return st.size();// 2、直接在范圍內統計 father[i] == i為父節點，其他的都是指向父節點的子節點int res = 0;for(int i = 0;i<len;i++){if(father[i]==i){res++;}}return res;}
};

3、684. 冗余連接

在一棵樹中，邊的數量比節點的數量少 1。如果一棵樹有 n 個節點，則這棵樹有 n?1 條邊。這道題中的圖在樹的基礎上多了一條附加的邊，因此邊的數量也是 n。
樹是一個連通且無環的無向圖，在樹中多了一條附加的邊之后就會出現環，因此附加的邊即為導致環出現的邊。
可以通過并查集尋找附加的邊。初始時，每個節點都屬于不同的連通分量。遍歷每一條邊，判斷這條邊連接的兩個頂點是否屬于相同的連通分量。
并查集解決問題：**只有出現環時，才會出現兩個根相同。**如果一棵樹有 n 個節點，則這棵樹有 n?1 條邊。那么這兩個節點根一定不同。

樹可以看成是一個連通且無環的無向圖。

給定往一棵 n 個節點 (節點值 1～n) 的樹中添加一條邊后的圖。添加的邊的兩個頂點包含在 1 到 n
中間，且這條附加的邊不屬于樹中已存在的邊。圖的信息記錄于長度為 n 的二維數組 edges ，edges[i] = [ai, bi] 表示圖中在 ai 和 bi 之間存在一條邊。

請找出一條可以刪去的邊，刪除后可使得剩余部分是一個有著 n 個節點的樹。如果有多個答案，則返回數組 edges 中最后出現的那個。

示例 1：

輸入: edges = [[1,2], [1,3], [2,3]] 輸出: [2,3]

示例 2：

輸入: edges = [[1,2], [2,3], [3,4], [1,4], [1,5]] 輸出: [1,4]

提示:

n == edges.length
3 <= n <= 1000
edges[i].length == 2
1 <= ai < bi <= edges.length
ai != bi
edges 中無重復元素
給定的圖是連通的

/*思路：題目中有個環：環比樹路徑多，找到重復的路徑一般的樹，不會出現，同一個根，只有環才可能出現兩個節點的根一樣
*/class Solution {
public:int n = 1001;vector<int> father{vector<int>(n)};void init() {for (int i = 0; i < n; i++) {father[i] = i;}}int find(int a) {if (a == father[a])return a;elsereturn father[a] = find(father[a]);}void join(int a, int b) {a = find(a);b = find(b);if (a == b)return;father[a] = b;}vector<int> findRedundantConnection(vector<vector<int>>& edges) {init();vector<int> res;for (auto& a : edges) {if (find(a[0]) == find(a[1])) {res = a;break;}join(a[0], a[1]);}return res;}
};

4、 1061. 按字典序排列最小的等效字符串

給出長度相同的兩個字符串s1 和 s2 ，還有一個字符串 baseStr 。

其中 s1[i] 和 s2[i] 是一組等價字符。

舉個例子，如果 s1 = "abc" 且 s2 = "cde"，那么就有 'a' == 'c', 'b' == 'd', 'c' == 'e'。

等價字符遵循任何等價關系的一般規則：

自反性 ：'a' == 'a'
對稱性 ：'a' == 'b' 則必定有 'b' == 'a'
傳遞性 ：'a' == 'b' 且 'b' == 'c' 就表明 'a' == 'c'

例如， s1 = "abc" 和 s2 = "cde" 的等價信息和之前的例子一樣，那么 baseStr = "eed" , "acd" 或 "aab"，這三個字符串都是等價的，而 "aab" 是 baseStr 的按字典序最小的等價字符串

利用 s1 和 s2 的等價信息，找出并返回 baseStr 的按字典序排列最小的等價字符串。

示例 1：

輸入：s1 = "parker", s2 = "morris", baseStr = "parser"
輸出："makkek"
解釋：根據 A 和 B 中的等價信息，我們可以將這些字符分為 [m,p], [a,o], [k,r,s], [e,i] 共 4 組。每組中的字符都是等價的，并按字典序排列。所以答案是 "makkek"。

示例 2：

輸入：s1 = "hello", s2 = "world", baseStr = "hold"
輸出："hdld"
解釋：根據 A 和 B 中的等價信息，我們可以將這些字符分為 [h,w], [d,e,o], [l,r] 共 3 組。所以只有 S 中的第二個字符 'o' 變成 'd'，最后答案為 "hdld"。

示例 3：

輸入：s1 = "leetcode", s2 = "programs", baseStr = "sourcecode"
輸出："aauaaaaada"
解釋：我們可以把 A 和 B 中的等價字符分為 [a,o,e,r,s,c], [l,p], [g,t] 和 [d,m] 共 4 組，因此 S 中除了 'u' 和 'd' 之外的所有字母都轉化成了 'a'，最后答案為 "aauaaaaada"。

提示：

1 <= s1.length, s2.length, baseStr <= 1000
s1.length == s2.length
字符串s1, s2, and baseStr 僅由從 'a' 到 'z' 的小寫英文字母組成。

/*思路：使用并查集將根節點都變成最小的，再遍歷一下全換成根就行有個坑點：if (find(s1[i]-'a') > find(s2[i]-'a'))這里需要每次找到根，再去判斷。
*/class Solution {
public:int n = 50;vector<int> father = vector<int>(n);void init() {for (int i = 0; i < father.size(); i++) {father[i] = i;}}int find(int a) {if (father[a] == a)return a;elsereturn father[a] = find(father[a]);}bool same(int a, int b) {a = find(a);b = find(b);return a == b;}void join(int a, int b) {a = find(a);b = find(b);if (a == b)return;elsefather[a] = b;}string smallestEquivalentString(string s1, string s2, string baseStr) {init();for (int i = 0; i < s1.size(); i++) {if (find(s1[i]-'a') > find(s2[i]-'a'))join(s1[i] - 'a', s2[i] - 'a');elsejoin(s2[i] - 'a', s1[i] - 'a');}for (auto& a : baseStr) {a = find(a-'a')+'a';}return baseStr;}
};

5、990. 等式方程的可滿足性

給定一個由表示變量之間關系的字符串方程組成的數組，每個字符串方程 equations[i] 的長度為 4，并采用兩種不同的形式之一："a==b" 或 "a!=b"。在這里，a 和 b 是小寫字母（不一定不同），表示單字母變量名。

只有當可以將整數分配給變量名，以便滿足所有給定的方程時才返回 true，否則返回 false。

示例 1：

輸入：["a==b","b!=a"]
輸出：false
解釋：如果我們指定，a = 1 且 b = 1，那么可以滿足第一個方程，但無法滿足第二個方程。沒有辦法分配變量同時滿足這兩個方程。

示例 2：

輸入：["b==a","a==b"]
輸出：true
解釋：我們可以指定 a = 1 且 b = 1 以滿足滿足這兩個方程。

示例 3：

輸入：["a==b","b==c","a==c"]
輸出：true

示例 4：

輸入：["a==b","b!=c","c==a"]
輸出：false

示例 5：

輸入：["c==c","b==d","x!=z"]
輸出：true

提示：

1 <= equations.length <= 500
equations[i].length == 4
equations[i][0] 和 equations[i][3] 是小寫字母
equations[i][1] 要么是 '='，要么是 '!'
equations[i][2] 是 '='

/*思路：取等號說明可以加入并查集使用不等號進行判斷：如果不等號兩邊是同一個根：說明之前等號過注意：并查集加入似乎跟前后的順序沒有關系
*/class Solution {
public:int n = 30;vector<int> father = vector<int>(n);void init() {for (int i = 0; i < n; i++) {father[i] = i;}}int find(int a) {if (a == father[a])return a;return father[a] = find(father[a]);}void join(int a, int b) {a = find(a);b = find(b);if (a == b)return;father[a] = b;}bool equationsPossible(vector<string>& equations) {init();for (auto& a : equations) {if (a[1] == '=')join(a[0] - 'a', a[3] - 'a');}for (auto& a : equations) {if (a[1] == '!') {if (find(a[0] - 'a') == find(a[3] - 'a')) {return false;}}}return true;}
};

6、947. 移除最多的同行或同列石頭

解決連通性問題：記模板：x->y+max，如果聯通則最后結果都是最右邊的y+max
把二維坐標平面上的石頭想象成圖的頂點，如果兩個石頭橫坐標相同、或者縱坐標相同，在它們之間形成一條邊。

根據可以移除石頭的規則：如果一塊石頭的同行或者同列上有其他石頭存在，那么就可以移除這塊石頭。可以發現：一定可以把一個連通圖里的所有頂點根據這個規則刪到只剩下一個頂點。

n 塊石頭放置在二維平面中的一些整數坐標點上。每個坐標點上最多只能有一塊石頭。

如果一塊石頭的 同行或者同列 上有其他石頭存在，那么就可以移除這塊石頭。

給你一個長度為 n 的數組 stones ，其中 stones[i] = [xi, yi] 表示第 i 塊石頭的位置，返回 可以移除的石子 的最大數量。

示例 1：

1 1 0
1 0 1
0 1 1-》0->100  0->100->101 0
1->101  0           1->101->102
0       2->101->102 102->102102  102  0
102  0    102
0    102  1020 1 
1 0 0    0->1
1->0 00   0->101
1->100 0輸入：stones = [[0,0],[0,1],[1,0],[1,2],[2,1],[2,2]]
輸出：5
解釋：一種移除 5 塊石頭的方法如下所示：
1. 移除石頭 [2,2] ，因為它和 [2,1] 同行。
2. 移除石頭 [2,1] ，因為它和 [0,1] 同列。
3. 移除石頭 [1,2] ，因為它和 [1,0] 同行。
4. 移除石頭 [1,0] ，因為它和 [0,0] 同列。
5. 移除石頭 [0,1] ，因為它和 [0,0] 同行。
石頭 [0,0] 不能移除，因為它沒有與另一塊石頭同行/列。

示例 2：

1 0 1
0 1 0
1 0 1
輸入：stones = [[0,0],[0,2],[1,1],[2,0],[2,2]]
輸出：3
解釋：一種移除 3 塊石頭的方法如下所示：
1. 移除石頭 [2,2] ，因為它和 [2,0] 同行。
2. 移除石頭 [2,0] ，因為它和 [0,0] 同列。
3. 移除石頭 [0,2] ，因為它和 [0,0] 同行。
石頭 [0,0] 和 [1,1] 不能移除，因為它們沒有與另一塊石頭同行/列。

示例 3：

輸入：stones = [[0,0]]
輸出：0
解釋：[0,0] 是平面上唯一一塊石頭，所以不可以移除它。

提示：

1 <= stones.length <= 1000
0 <= xi, yi <= 104
不會有兩塊石頭放在同一個坐標點上

/*思路難以想象：只能記模板：把坐標x->y+10000上就能實現連通性分析問題：只要在坐標上是聯通的就可以得到同一個結果：同一個根：為什么?可以模擬出來，但是想不通注意：Y需要加上最大值：為了解決0  1 1  0的問題最后的結果都是：y的值最右邊y的值
*/class Solution {
public:int n = 51000;vector<int> father = vector<int>(n);void init() {for (int i = 0; i < father.size(); i++) {father[i] = i;}}int find(int a) {if (father[a] == a)return a;elsereturn father[a] = find(father[a]);}bool same(int a, int b) {a = find(a);b = find(b);return a == b;}void join(int a, int b) {a = find(a);b = find(b);if (a == b)return;elsefather[a] = b;}int removeStones(vector<vector<int>>& stones) {init();for (auto a : stones) {join(a[0], a[1] + 20005);}unordered_map<int, int> mp;for (auto a : stones) {mp[find(a[0])] = 1;}return stones.size() - mp.size();}
};