我們考慮如何計(jì)算一個(gè)圖連通分量的個(gè)數(shù). 假定簡(jiǎn)單無向圖
G
G
G有兩個(gè)連通分量(子圖)
G
1
,
G
2
G_1, G_2
G1?,G2?, 如下圖所示:
一個(gè)很自然的想法是, 要想求連通分量個(gè)數(shù), 我們可以使用Full-DFS算法, 也就是我們從某個(gè)點(diǎn)開始深度優(yōu)先搜索, 并標(biāo)記訪問過的元素. 隨后挨個(gè)頂點(diǎn)判斷, 如果某個(gè)點(diǎn)沒有被訪問過, 則接著從該點(diǎn)進(jìn)行深度優(yōu)先搜索, 這樣深度優(yōu)先搜索的次數(shù)就是連通量的個(gè)數(shù).
除此之外, 我們還可以用并查集來求圖中連通分量的個(gè)數(shù). 并查集, 顧名思義, 有并與查兩部分. 并, 就是合并(join, union), 即利用某種規(guī)則將兩個(gè)頂點(diǎn)合并為一個(gè)連通分量. 查, 就是查詢(find), 用以查詢某個(gè)節(jié)點(diǎn)所屬連通分量的代表性節(jié)點(diǎn).
例如, 某個(gè)單位里, 有兩個(gè)幫派. 一個(gè)員工A和另一個(gè)員工B相遇了, 兩個(gè)人想知道自己是不是同屬一個(gè)幫派. 于是, 兩個(gè)人可以互相報(bào)上自己幫派的老大, 是局長(zhǎng)還是書記. 如果兩個(gè)人的老大一樣, 則兩個(gè)人就是同屬一個(gè)幫派, 否則不是.
抽象出來, 我們將每個(gè)連通分量都選出一個(gè)代表的節(jié)點(diǎn), 這個(gè)節(jié)點(diǎn)就是老大, 該連通分量中其他的節(jié)點(diǎn)或直接, 或間接地與老大相連. 一個(gè)單位幫派的個(gè)數(shù)可以用老大的個(gè)數(shù)來代表.
下面說具體如何去并, 查
1. 查, find一個(gè)連通圖總可以表示成一個(gè)生成樹(例如, 單位里的一個(gè)幫派總可以捋出來一個(gè)上下級(jí)關(guān)系), 例如,
G
1
G_1
G1?子圖中, 假設(shè)每個(gè)節(jié)點(diǎn)有編號(hào), 那么假定有如圖的一種連接關(guān)系(生成樹):
1是老大, 下面是2, 3, 4是老末. 如果我們用一個(gè)數(shù)組
p
a
r
e
n
t
[
N
]
parent[N]
parent[N]表示這種上下級(jí)關(guān)系, 也就是
p
a
r
e
n
t
[
i
]
=
j
parent[i]=j
parent[i]=j表示i的上級(jí)為j, 則上圖的關(guān)系可以表示為:
parent[4] = 2parent[2] = 1parent[3] = 1parent[1] = 1
所以, 只有老大的上級(jí)才是他自己. 如果給我們一個(gè)4, 想查一下, 4的老大是誰? 我們就可以這樣一層一層查上去:
parent[4] = 2parent[2] = 1parent[1] = 1, Done!!!
當(dāng)找到滿足parent[i] = i的i, 就表示找到了老大(子圖的代表)為i.
我們可以用代碼這樣表示:
重慶分公司
重慶分公司
int find(int x) {while (parent[x] != x) x = parent[x]; // 只要沒找到, 就沿著上級(jí)繼續(xù)找
return x; // 找到了, 返回
}但是, 假如一個(gè)倒霉催的結(jié)構(gòu)是這樣的:
那我們就需要花費(fèi)
O
(
n
)
O(n)
O(n)的時(shí)間去找, 這是因?yàn)椴黄胶獾臉鋾?huì)帶來更大的時(shí)間復(fù)雜度(最壞的情況為
O
(
n
)
O(n)
O(n)). 為此, 既然我們只是找老大, 我們直接讓每個(gè)人直接對(duì)老大負(fù)責(zé)不好么?
我們?nèi)绾巫龅竭@一點(diǎn)? 我們用遞歸來實(shí)現(xiàn). 對(duì)于不滿足parent[i] = i的i, 我們直接讓i的上級(jí)parent[i]等于老大, 也就是parent[i] = find(parent[i]), 這樣遞歸下去就可以達(dá)到上圖的結(jié)果. 需要說明的是, 這樣整理好之后, 以后的查詢才會(huì)省時(shí)間. 換言之, 第一次是不會(huì)節(jié)約時(shí)間的. 于是現(xiàn)在的find函數(shù)可以寫為:
int find(int i) {if (parent[i] != i) // 沒有找到
parent[i] = find(parent[i]); // 讓i的上級(jí)是老大
return parent[i]; // 返回老大
}如果說, 單位里的兩個(gè)派別準(zhǔn)備重修舊好, 也就是兩個(gè)派別要合并. 然而, 一個(gè)派別只能有一個(gè)老大, 所以兩個(gè)派別的老大就必須有一個(gè)要屈尊, 不再當(dāng)老大, 成為另一個(gè)老大的下屬, 這樣的話, 不論兩個(gè)派別的哪個(gè)人, 最終都可以查詢到新的老大, 這就是并的過程, 用下圖表示:
代碼這么來描述:
void unoin(int x, int y){// 合并倆派別, x, y為其中的成員
int px = find(x), py = find(y); // 找到他們各自的老大
if (px != py) parent[px] = py; // 讓px的老大的老大為py
}那么假如我們想指定一種合并的規(guī)則, 應(yīng)該如何做呢? 假設(shè)我們標(biāo)記節(jié)點(diǎn)的深度, 如圖所示:
因此, 為了不讓樹產(chǎn)生退化(合并后左右子樹的高度差盡可能小), 我們將深度小的合并到深度大的. 如果二者的深度相同, 則可以隨便指定一個(gè)作為新老大, 隨后將新老大的權(quán)值加1, 如圖:
代碼如下:
void unoin(int x, int y) {// 尋找x, y的老大
int px = find(x), py = find(y);
if (px != py) { // 如果x的權(quán)重大 讓y的老大為x
if (rank[px] >rank[py]) parent[py] = px;
else {// 否則 讓x的老大為y
if (rank[px] == rank[py]) rank[py]++; // 如果權(quán)重相等 則先將y的權(quán)重加1
parent[px] = py;
}
}
}下面用幾道例題說明并查集的使用. 難度從低到高.
3.1 最長(zhǎng)連續(xù)序列題目鏈接: LeetCode128
這個(gè)題讓我們?cè)跀?shù)組中找到一個(gè)最長(zhǎng)的連續(xù)數(shù)字序列. 如果我們將元素視為圖里的節(jié)點(diǎn), 每一段連續(xù)的數(shù)字序列作為一個(gè)子圖, 就是要找到節(jié)點(diǎn)最多的子圖.
為此, 我們對(duì)于數(shù)組元素num, 假如num + 1也在數(shù)組中, 則將num所在的子圖與num + 1所在的子圖并在一起. 除此之外, 我們還需要用一個(gè)額外的哈希表記錄每個(gè)子圖的大小, 鍵為子圖的老大, 值為子圖的大小.
代碼:
class Solution {public:
unordered_mappre, regionResult; // pre: 儲(chǔ)存父節(jié)點(diǎn) regionResult: 節(jié)點(diǎn)所在連通域面積
int find(int x) {// 查
if (x == pre[x]) return x;
else {pre[x] = find(pre[x]);
return pre[x];
}
}
int merge(int x, int y) {// 并
x = find(x), y = find(y);
if (x == y) return regionResult[x];
// 若不相等 并到一起
pre[y] = x;
regionResult[x] += regionResult[y]; // 把大小加一起并返回
return regionResult[x];
}
int longestConsecutive(vector& nums) {if (!nums.size()) return 0;
int result = 1;
// 初始化
for (int num : nums) {pre[num] = num;
regionResult[num] = 1;
}
// 合并相鄰數(shù) 并更新結(jié)果 注意只合并num與num+1 不需要合并num與num-1 否則重復(fù)
for (int num : nums) {if (pre.count(num + 1))
result = max(result, merge(num, num + 1));
}
return result;
}
}; 題目鏈接: Acwing4796
這個(gè)題是說, 有一個(gè)試管, 初始時(shí)危險(xiǎn)值為1. 現(xiàn)在往里面導(dǎo)入物質(zhì), 假如要倒入的物質(zhì)可以和試管里面任一一種物質(zhì)反應(yīng), 則將危險(xiǎn)值乘2. 問可以達(dá)到的大危險(xiǎn)值為多少.
我們可以構(gòu)建圖來解決這個(gè)問題. 假如a與b反應(yīng), b與c反應(yīng), 則a, b, c可以構(gòu)成一個(gè)連通子圖. 于是n個(gè)物質(zhì)就構(gòu)成了若干個(gè)連通子圖, 每個(gè)子圖中的物質(zhì)可以與子圖中其他若干個(gè)物質(zhì)發(fā)生反應(yīng). 所以, 對(duì)于一個(gè)有t個(gè)節(jié)點(diǎn)的子圖, 可以達(dá)到大的危險(xiǎn)值為
2
t
?
1
2^{t-1}
2t?1, 證明如下:
例如假設(shè)四種物質(zhì)a,b,c,d的反應(yīng)關(guān)系如下(如果不是嚴(yán)格的樹(即有環(huán)), 也一定可以等價(jià)成如下的形式):
那么只要按照廣度優(yōu)先搜索的順序倒入a->b->c->d, 就可以達(dá)到2^3=8的危險(xiǎn)度. 且不同子圖間是孤立的, 因此假設(shè)一共有k個(gè)子圖, 每個(gè)子圖的節(jié)點(diǎn)個(gè)數(shù)分別為
a
0
,
.
.
.
,
a
k
?
1
a_0, ..., a_{k-1}
a0?,...,ak?1?, 則大的危險(xiǎn)程度為
2
a
0
?
1
?
2
a
1
?
1
?
?
?
?
2
a
k
?
1
?
1
=
2
n
?
k
2^{a_0-1}·2^{a_1-1}····2^{a_{k-1}-1}=2^{n-k}
2a0??1?2a1??1????2ak?1??1=2n?k
為此, 我們只需要求出連通子圖的個(gè)數(shù)即可.
代碼:
#include#include#include
using namespace std;
const int N = 1010;
int parent[N]; // parent數(shù)組
int find(int x) {if (parent[x] != x) {parent[x] = find(parent[x]);
}
return parent[x];
}
int main()
{int n, m;
cin >>n >>m;
// 初始化并查集 每個(gè)指向自己
for (int i = 0; i< n; i ++ )
parent[i] = i;
int result = n; // 初始n個(gè)子圖
while (m -- ) {int x, y;
cin >>x >>y; // 能反應(yīng)的兩種物質(zhì)
// 找到老大
x = find(x); y = find(y);
if (x != y) {// 合并兩個(gè)子圖
parent[x] = y;
result --;
}
}
cout<< (1LL<< (n - result))<< "\n";
return 0;
} 題目鏈接: LeetCode200
這個(gè)題的一種做法是, 跟玩掃雷一樣, 但凡是掃到一個(gè)1, 那么執(zhí)行深度優(yōu)先搜索, 將與其相連的1都掃成0. 這樣再碰到下一個(gè)1時(shí), 一定是另一個(gè)島嶼, 所以島嶼的數(shù)量就是執(zhí)行深度優(yōu)先搜索的次數(shù). 代碼:
class Solution {private:
int rows = 0, cols = 0;
public:
void dfs(vector>& grid, int row, int col) {grid[row][col] = '0'; // 標(biāo)記為0
// 上下左右, 深度優(yōu)先
if (row >0 && grid[row - 1][col] == '1') dfs(grid, row - 1, col);
if (col >0 && grid[row][col - 1] == '1') dfs(grid, row, col - 1);
if (row< rows - 1 && grid[row + 1][col] == '1') dfs(grid, row + 1, col);
if (col< cols - 1 && grid[row][col + 1] == '1') dfs(grid, row, col + 1);
}
int numIslands(vector>& grid) {this->rows = grid.size();
this->cols = grid[0].size();
int result = 0;
for (int row = 0; row< rows; row ++) {for (int col = 0; col< cols; col ++) {if (grid[row][col] == '1') {dfs(grid, row, col);
result ++;
}
}
}
return result;
}
}; 也可以用并查集來做. 每個(gè)'1', 我們都將其與周圍的'1'連通, 則島嶼的數(shù)量就是連通圖的數(shù)量.
class UnionFind {public:
UnionFind(vector>& grid) {count = 0;
int m = grid.size();
int n = grid[0].size();
for (int i = 0; i< m; ++i) {for (int j = 0; j< n; ++j) {if (grid[i][j] == '1') {parent.push_back(i * n + j);
++count;
}
else {parent.push_back(-1);
}
rank.push_back(0);
}
}
}
int find(int i) {if (parent[i] != i) {parent[i] = find(parent[i]);
}
return parent[i];
}
void unite(int x, int y) {int rootx = find(x);
int rooty = find(y);
if (rootx != rooty) {if (rank[rootx] >rank[rooty])
parent[rooty] = rootx;
else {if (rank[rootx] == rank[rooty]) rank[rooty] ++;
parent[rootx] = rooty;
}
count --;
}
}
int getCount() const {return count;
}
private:
vectorparent;
vectorrank;
int count;
};
class Solution {public:
int numIslands(vector>& grid) {int nr = grid.size();
if (!nr) return 0;
int nc = grid[0].size();
UnionFind uf(grid);
int num_islands = 0;
for (int r = 0; r< nr; ++r) {for (int c = 0; c< nc; ++c) {if (grid[r][c] == '1') {grid[r][c] = '0';
if (r - 1 >= 0 && grid[r-1][c] == '1') uf.unite(r * nc + c, (r-1) * nc + c);
if (r + 1< nr && grid[r+1][c] == '1') uf.unite(r * nc + c, (r+1) * nc + c);
if (c - 1 >= 0 && grid[r][c-1] == '1') uf.unite(r * nc + c, r * nc + c - 1);
if (c + 1< nc && grid[r][c+1] == '1') uf.unite(r * nc + c, r * nc + c + 1);
}
}
}
return uf.getCount();
}
};
你是否還在尋找穩(wěn)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機(jī)房具備T級(jí)流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級(jí)服務(wù)器適合批量采購，新人活動(dòng)首月15元起，快前往官網(wǎng)查看詳情吧
