【一百零三】【算法分析與設計】并查集,并查集的實現,P3367 【模板】并查集

并查集的實現

描述

給定一個沒有重復值的整形數組arr，初始時認為arr中每一個數各自都是一個單獨的集合。請設計一種叫UnionFind的結構，并提供以下兩個操作。

boolean isSameSet(int a, int b): 查詢a和b這兩個數是否屬于一個集合

void union(int a, int b): 把a所在的集合與b所在的集合合并在一起，原本兩個集合各自的元素以后都算作同一個集合

[要求]

如果調用isSameSet和union的總次數逼近或超過O(N)，請做到單次調用isSameSet或union方法的平均時間復雜度為O(1)

輸入描述：

第一行兩個整數N, M。分別表示數組大小、操作次數接下來M行，每行有一個整數opt 若opt = 1，后面有兩個數x, y，表示查詢(x, y)這兩個數是否屬于同一個集合若opt = 2，后面有兩個數x, y，表示把x, y所在的集合合并在一起

輸出描述：

對于每個opt = 1的操作，若為真則輸出"Yes"，否則輸出"No"

示例1

輸入：
4 5
1 1 2
2 2 3
2 1 3
1 1 1
1 2 3
復制

輸出：
No
Yes
Yes
復制

說明：

每次2操作后的集合為 ({1}, {2}, {3}, {4}) ({1}, {2, 3}, {4}) ({1, 2, 3}, {4})

備注：

$\leqslant N, M \leqslant 10^6\\1?N,M?10^6$

保證 $\leqslant x, y \leqslant N$
保證 $1 ? x, y ? N$

一般寫法

#include<bits/stdc++.h>
using namespace std;#define int long long
#define endl '\n'
#define FAST() ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)#define p pair<int,int> 
#define ff first
#define ss second #define ltu(i,a,b) for(int i=a;i<=b;i++)
#define utl(i,a,b) for(int i=a;i>=b;i--)int n,m; // 定義兩個整型變量n和m，表示數組大小和操作次數
struct node{int op,x,y; // 定義一個結構體node，包含三個整型變量op, x, y
};
vector<node> readd; // 定義一個存儲node結構體的向量readdvector<int>father; // 定義一個整型向量father，用來存儲每個節點的父節點
vector<int>stackk; // 定義一個整型向量stackk，用來存儲路徑上的節點// findd函數用于查找節點i的根節點
int findd(int i){while(!(father[i]==i)){ // 如果節點i不是自己的父節點i=father[i]; // 將i更新為它的父節點stackk.push_back(i); // 將節點i壓入stackk}while(!stackk.empty()){ // 當stackk不為空時father[stackk.back()]=i; // 將stackk中的每個節點的父節點更新為istackk.pop_back(); // 彈出stackk的最后一個元素}return i; // 返回根節點
}// isSameSet函數用于判斷兩個節點x和y是否屬于同一個集合
bool isSameSet(int x,int y){return findd(x)==findd(y); // 比較x和y的根節點是否相同
}// unionn函數用于將兩個節點x和y所在的集合合并
void unionn(int x,int y){father[findd(x)]=findd(y); // 將x的根節點的父節點設為y的根節點
}// solve函數用于處理所有的操作
void solve(){father.assign(n+5,0); // 初始化father向量，大小為n+5stackk.clear(); // 清空stackkltu(i,0,n+5-1){ // 遍歷每個節點father[i]=i; // 初始化每個節點的父節點為自己}for(auto&xx:readd){ // 遍歷所有的操作if(xx.op==1){ // 如果操作類型為1，表示查詢操作if(isSameSet(xx.x,xx.y)){ // 判斷x和y是否屬于同一個集合cout<<"Yes"<<endl; // 是同一個集合則輸出Yes}else{cout<<"No"<<endl; // 否則輸出No}}else{ // 如果操作類型為2，表示合并操作unionn(xx.x,xx.y); // 合并x和y所在的集合}}
}// main函數是程序的入口
signed main(){FAST(); // 加速輸入輸出cin>>n>>m; // 輸入n和mreadd.clear(); // 清空readd向量ltu(i,1,m){ // 遍歷m次node temp; // 定義一個臨時node變量cin>>temp.op>>temp.x>>temp.y; // 輸入操作類型和對應的x, yreadd.push_back(temp); // 將temp壓入readd向量}solve(); // 調用solve函數處理操作
}

進階寫法

在這里插入圖片描述

#include<bits/stdc++.h> // 引入所有標準庫頭文件
using namespace std;#define int long long // 使用長整型定義int，方便處理大數
#define endl '\n' // 定義換行符
#define FAST() ios::sync_with_stdio(0),cin.tie(0),cout.tie(0) // 加速輸入輸出#define p pair<int,int> // 定義一個整型對的類型別名
#define ff first // 定義first的別名
#define ss second // 定義second的別名#define ltu(i,a,b) for(int i=a;i<=b;i++) // 定義從a到b的循環
#define utl(i,a,b) for(int i=a;i>=b;i--) // 定義從a到b的逆向循環int n,m; // 定義兩個長整型變量n和m，表示元素個數和操作次數
struct node{int op,x,y; // 定義一個結構體node，包含三個長整型變量op, x, y
};
vector<node> readd; // 定義一個存儲node結構體的向量readd
vector<int> father; // 定義一個長整型向量father，用來存儲每個節點的父節點// findd函數用于查找節點i的根節點
int findd(int i){if(father[i]!=i) father[i]=findd(father[i]); // 如果節點i不是自己的父節點，遞歸查找父節點并路徑壓縮return father[i]; // 返回根節點
}// solve函數用于處理所有的操作
void solve(){father.assign(n+5,0); // 初始化father向量，大小為n+5ltu(i,0,n+5-1){ // 遍歷每個節點father[i]=i; // 初始化每個節點的父節點為自己}for(auto& xx : readd){ // 遍歷所有的操作if(xx.op == 1){ // 如果操作類型為1，表示查詢操作if(findd(xx.x) == findd(xx.y)){ // 判斷x和y的根節點是否相同cout << "Yes" << endl; // 是同一個集合則輸出Yes} else {cout << "No" << endl; // 否則輸出No}} else { // 如果操作類型為2，表示合并操作father[findd(xx.x)] = findd(xx.y); // 將x的根節點的父節點設為y的根節點}}
}// main函數是程序的入口
signed main(){FAST(); // 加速輸入輸出cin >> n >> m; // 輸入n和mreadd.clear(); // 清空readd向量ltu(i,1,m){ // 遍歷m次node temp; // 定義一個臨時node變量cin >> temp.op >> temp.x >> temp.y; // 輸入操作類型和對應的x, yreadd.push_back(temp); // 將temp壓入readd向量}solve(); // 調用solve函數處理操作
}

P3367 【模板】并查集

【模板】并查集

題目描述

如題，現在有一個并查集，你需要完成合并和查詢操作。

輸入格式

第一行包含兩個整數 $N, M$ ,表示共有 $N$ 個元i素和 $M$ 個操作。

接下來 $M$ 行，每行包含三個整數 $Z\_i,X\_i,Y\_i$ 。

當 $Z\_i=1$ 時，將 $X\_i$ 與 $Y\_i$ 所在的集合合并。

當 $Z\_i=2$ 時，輸出 $X\_i$ 與 $Y\_i$ 是否在同一集合內，是的輸出 Y ；否則輸出 N 。

輸出格式

對于每一個 $Z\_i=2$ 的操作，都有一行輸出，每行包含一個大寫字母，為 Y 或者 N 。

樣例 #1

樣例輸入 #1
4 7
2 1 2
1 1 2
2 1 2
1 3 4
2 1 4
1 2 3
2 1 4
樣例輸出 #1
N
Y
N
Y
提示

對于 $30\%$ 的數據， $\le 10，M \le 20$ 。

對于 $70\%$ 的數據， $\le 100，M \le 10^3$ 。

對于 $100\%$ 的數據， $1\le N \le 10^4$ ， $1\le M \le 2\times 10^5$ ， $\le X\_i, Y\_i \le N$ ， $Z\_i \in \{ 1, 2 \}$ 。

一般寫法

#include<bits/stdc++.h>
using namespace std;#define int long long // 使用長整型定義int，方便處理大數
#define endl '\n' // 定義換行符
#define FAST() ios::sync_with_stdio(0),cin.tie(0),cout.tie(0) // 加速輸入輸出#define p pair<int,int>
#define ff first
#define ss second 
#define ltu(i,a,b) for(int i=a;i<=b;i++) // 定義從a到b的循環
#define utl(i,a,b) for(int i=a;i>=b;i--) // 定義從a到b的逆向循環int n, m; // 定義兩個長整型變量n和m，表示元素個數和操作次數
struct node {int op, x, y; // 定義一個結構體node，包含三個長整型變量op, x, y
};
vector<node> readd; // 定義一個存儲node結構體的向量readdvector<int> father; // 定義一個長整型向量father，用來存儲每個節點的父節點
vector<int> st; // 定義一個長整型向量st，用來存儲路徑上的節點// findd函數用于查找節點i的根節點
int findd(int i) {while (!(father[i] == i)) { // 如果節點i不是自己的父節點i = father[i]; // 將i更新為它的父節點st.push_back(i); // 將節點i壓入st}while (!st.empty()) { // 當st不為空時father[st.back()] = i; // 將st中的每個節點的父節點更新為ist.pop_back(); // 彈出st的最后一個元素}return i; // 返回根節點
}// isSameSet函數用于判斷兩個節點x和y是否屬于同一個集合
bool isSameSet(int x, int y) {return findd(x) == findd(y); // 比較x和y的根節點是否相同
}// unionn函數用于將兩個節點x和y所在的集合合并
void unionn(int x, int y) {father[findd(x)] = findd(y); // 將x的根節點的父節點設為y的根節點
}// solve函數用于處理所有的操作
void solve() {father.assign(n + 5, 0); // 初始化father向量，大小為n+5ltu(i, 0, n + 5 - 1) { // 遍歷每個節點father[i] = i; // 初始化每個節點的父節點為自己}st.clear(); // 清空stfor (auto& xx : readd) { // 遍歷所有的操作int op = xx.op, x = xx.x, y = xx.y; // 獲取操作類型和對應的x, yif (op == 1) { // 如果操作類型為1，表示合并操作unionn(x, y); // 合并x和y所在的集合} else { // 如果操作類型為2，表示查詢操作if (isSameSet(x, y)) cout << "Y" << endl; // 是同一個集合則輸出Yelse cout << "N" << endl; // 否則輸出N}}
}// main函數是程序的入口
signed main() {FAST(); // 加速輸入輸出cin >> n >> m; // 輸入n和mreadd.clear(); // 清空readd向量ltu(i, 1, m) { // 遍歷m次node temp; // 定義一個臨時node變量cin >> temp.op >> temp.x >> temp.y; // 輸入操作類型和對應的x, yreadd.push_back(temp); // 將temp壓入readd向量}solve(); // 調用solve函數處理操作
}

進階寫法

#include<bits/stdc++.h> // 引入所有標準庫頭文件
using namespace std;#define int long long // 使用長整型定義int，方便處理大數
#define endl '\n' // 定義換行符
#define FAST() ios::sync_with_stdio(0) // 加速輸入輸出#define p pair<int,int> // 定義一個整型對的類型別名
#define ff first // 定義first的別名
#define ss second // 定義second的別名#define ltu(i,a,b) for(int i=a;i<=b;i++) // 定義從a到b的循環
#define utl(i,a,b) for(int i=a;i>=b;i--) // 定義從a到b的逆向循環int n, m; // 定義兩個長整型變量n和m，表示元素個數和操作次數
struct node {int op, x, y; // 定義一個結構體node，包含三個長整型變量op, x, y
};
vector<node> readd; // 定義一個存儲node結構體的向量readd
vector<int> father; // 定義一個長整型向量father，用來存儲每個節點的父節點// findd函數用于查找節點i的根節點
int findd(int i) {if (father[i] != i) father[i] = findd(father[i]); // 如果節點i不是自己的父節點，遞歸查找父節點并路徑壓縮return father[i]; // 返回根節點
}// solve函數用于處理所有的操作
void solve() {father.assign(n + 5, 0); // 初始化father向量，大小為n+5ltu(i, 0, n + 5 - 1) father[i] = i; // 初始化每個節點的父節點為自己for (auto& xx : readd) { // 遍歷所有的操作if (xx.op == 1) { // 如果操作類型為1，表示合并操作father[findd(xx.x)] = findd(xx.y); // 將x的根節點的父節點設為y的根節點} else { // 如果操作類型為2，表示查詢操作if (findd(xx.x) == findd(xx.y)) cout << "Y" << endl; // 是同一個集合則輸出Yelse cout << "N" << endl; // 否則輸出N}}
}// main函數是程序的入口
signed main() {FAST(); // 加速輸入輸出cin >> n >> m; // 輸入n和mltu(i, 1, m) { // 遍歷m次node temp; // 定義一個臨時node變量cin >> temp.op >> temp.x >> temp.y; // 輸入操作類型和對應的x, yreadd.push_back(temp); // 將temp壓入readd向量}solve(); // 調用solve函數處理操作
}