#查并集理論知識(shí)
?
并查集用處：解決連通性問題
- 將兩個(gè)元素添加到一個(gè)集合中。
- 判斷兩個(gè)元素在不在同一個(gè)集合
思路：將三個(gè)元素A，B，C （分別是數(shù)字）放在同一個(gè)集合，其實(shí)就是將三個(gè)元素連通在一起，如何連通：只需要用一個(gè)一維數(shù)組來表示，即：father[A] = B，father[B] = C 這樣就表述 A 與 B 與 C連通了（有向連通圖）。如果幾個(gè)元素的根是同一個(gè)，代表在同一集合。
find的路徑壓縮：
就需要?路徑壓縮，將非根節(jié)點(diǎn)的所有節(jié)點(diǎn)直接指向根節(jié)點(diǎn)
路徑壓縮長一點(diǎn)寫：
int find(int u) {
if (u == father[u]) return u;
else return father[u] = find(father[u]); // 路徑壓縮
}?路徑壓縮短一點(diǎn)寫：
int find(int u) {
return u == father[u] ? u : father[u] = find(father[u]);
}?隨想錄的查并集模板：
int n = 1005; // n根據(jù)題目中節(jié)點(diǎn)數(shù)量而定，一般比節(jié)點(diǎn)數(shù)量大一點(diǎn)就好
vector<int> father = vector<int> (n, 0); // C++里的一種數(shù)組結(jié)構(gòu)
// 并查集初始化
void init() {
for (int i = 0; i < n; ++i) {
father[i] = i;
}
}
// 并查集里尋根的過程
int find(int u) {
return u == father[u] ? u : father[u] = find(father[u]); // 路徑壓縮
}
// 判斷 u 和 v是否找到同一個(gè)根
bool isSame(int u, int v) {
u = find(u);
v = find(v);
return u == v;
}
// 將v->u 這條邊加入并查集
void join(int u, int v) {
u = find(u); // 尋找u的根
v = find(v); // 尋找v的根
if (u == v) return ; // 如果發(fā)現(xiàn)根相同，則說明在一個(gè)集合，不用兩個(gè)節(jié)點(diǎn)相連直接返回
father[v] = u;
}#?1971.尋找圖中是否存在路徑??并查集基礎(chǔ)題目
我用dfs做的，自己處理edge信息，夢(mèng)回3343 3391了
void dfs(int start, int dest, vector<vector<int>>& edges, vector<vector<int>> &path, vector<bool> &v,bool &flag){
if(start==dest){
flag=true;
return;
}
v[start]=true;
for(int i=0;i<path[start].size();i++){
if(!v[path[start][i]]) dfs(path[start][i], dest,edges,path,v,flag);
}
}
bool validPath(int n, vector<vector<int>>& edges, int source, int dest) {
vector<vector<int>> path(n);
vector<bool> v(n,false);
bool flag=false;
for(int i=0;i<edges.size();i++){
//edges[i] = [ui, vi] edges[i][0] edges[i][1]
path[edges[i][0]].push_back(edges[i][1]);
path[edges[i][1]].push_back(edges[i][0]);
}
dfs(source,dest,edges,path,v,flag);
return flag;
}查并集做法：（要把模板學(xué)會(huì)記住）自己寫的：
int n=200001;
vector<int> father=vector<int> (n,0);
void init(){
for(int u=0;u<n;u++) father[u]=u;
}
int find(int u){
if(u==father[u]) return u;
return father[u]=find(father[u]);
}
bool isSame(int u, int v){
u=find(u);
v=find(v);
return u==v;
}
void join(int u, int v){
u=find(u);
v=find(v);
if(u!=v) father[u]=v;
}
bool validPath(int n, vector<vector<int>>& edges, int source, int dest) {
init();
for(int i=0;i<edges.size();i++){
join(edges[i][0],edges[i][1]);
}
return isSame(source,dest);
}記住，所有函數(shù)最外面這么寫會(huì)錯(cuò)：
int n=200001;
vector<int> father(n,0);?
但是vector<int> father = vector<int>(n,0);? 這樣寫就可以（我不知道為什么
因?yàn)椋涸贑++中，同一個(gè)編譯單元（通常就是一個(gè)源文件）內(nèi)的全局變量的初始化順序是不確定的。編譯器可能以任何順序初始化它們，這個(gè)順序通常取決于編譯器的實(shí)現(xiàn)，是不可預(yù)測(cè)的。
#684.冗余連接?
我沒想到思路
判斷成環(huán)：已經(jīng)有同樣的根，但是又來一個(gè)edge連接兩者。文章來源：http://www.zghlxwxcb.cn/news/detail-601012.html
join易錯(cuò)點(diǎn)：最后一步 father[u]=v, father[v]=u 都可以，但是被賦值的一定要是father，不能反文章來源地址http://www.zghlxwxcb.cn/news/detail-601012.html
int n=1001;
vector<int> father=vector<int>(n,0);
void init(){
for(int u=0;u<n;u++) father[u]=u;
}
int find(int u){
if(u==father[u]) return u;
return father[u]=find(father[u]);
}
void join(int u, int v){
u=find(u);
v=find(v);
if(u!=v) father[v]=u;
}
bool isSame(int u, int v){
u=find(u);
v=find(v);
return u==v;
}
vector<int> findRedundantConnection(vector<vector<int>>& edges) {
init();
for(int i=0;i<edges.size();i++){
if(isSame(edges[i][0],edges[i][1])) return edges[i];
join(edges[i][0],edges[i][1]);
}
return {};
}到了這里，關(guān)于代碼隨想錄| 圖論04 查并集 ●查并集理論知識(shí) ●1971.尋找圖中是否存在路徑 ●684.冗余連接 ●685.冗余連接II的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
