基本概念
? 并查集是一種維護集合的資料結構，“并”，“查”，“集” 三個字分別取自 Union（合并），Find（查找），Set（集合），并查集是若干個不相交集合，能夠在 \(O(1)\) 實作兩個集合的合并，判斷兩個元素是否屬于同一集合應用，如其求無向圖的連通分量個數、實作kruskal演算法求最小生成樹，
并查集的實作方法就是一個陣列：
int pre[N];
其中 pre[i] 表示元素 i 結點的父節點，pre[i] 和 i 結點屬于同一集合，例如：pre[1] = 2 就表明元素1的父節點是元素2，元素1和元素2屬于同一集合，如果 pre[i]==i 則說明元素 i 是該集合的根結點，對于同一個集合來說，只存在一個根結點，
實作
準備作業
初始化一個pre陣列，用于記錄了每個節點屬于哪個集合；初始時陣列內的值與陣列的下角標一致，即每個數字都自己一個集合，
void initialize(int n) {
for (int i = 1; i <= n; i++) {
pre[i] = i;
}
}
查找操作
查找的目的是找到集合的 根結點 Big Boss，而不是前驅，因為前驅不一定是根結點，比如圖中的5，我們要找到的是3，而不是4，
看這幅圖，我們可以知道，當出現 pre[x]==x 時，證明找到了 Big Boss，
這里出現了一個問題，5和4的“頂頭上司”都是3，但是5卻要多走了一步，如果這個層級更多，那勢必會降低演算法的效率，
于是就有了在查找程序中的路徑壓縮
//查找
int Find(int x) {
if (pre[x] == x)return x;
return pre[x] = Find(pre[x]);
////你爸爸的爸爸就是你的爸爸
}
合并操作
初始三個節點，各自為一個集合
如下圖，合并3，4操作，此時3和4合并為一個集合，3掛在4上，還是4掛在3上都是一樣的，它們都表示3和4是同一個集合，只是集合的Big Boss不一樣，
我們繼續進行合并4,5操作，通過路徑壓縮我們獲得了右邊的形式，此時三個數已經為同一個集合了，
//合并
void Union(int x, int y) {
int fx = Find(x), fy = Find(y);
//如果x,y已經是同一集合了，回傳
if (fx == fy) return;
//這里通過深度來確定fx掛fy上，還是fy掛在fx上，實際意義不大，就簡單點寫了，
pre[fy] = fx;
}
完整代碼，這鬼東西好用就好用在很短，真的太好寫了
int pre[5001];
void initialize(int n) {
for (int i = 1; i <= n; i++) {
pre[i] = i;
}
}
int Find(int x) {
if (x == pre[x])return pre[x];
else return pre[x] = Find(pre[x]);
}
void Union(int x, int y) {
int fx = Find(x), fy = Find(y);
if (fx == fy) return;
pre[fy] = fx;
}
例題
標準模板題
HDU 1232 ：http://acm.hdu.edu.cn/showproblem.php?pid=1232
基本思想是：N個節點，最少需要 N-1 根線連起來， 把輸入的城鎮全部進行Union，如果這兩個城鎮不連通，N--，最后輸出 N - 1就是答案，
#include<stdio.h>
int Pre[1001];
//查找
int Find(int x) {
if (Pre[x] == x)return x;
return Pre[x] = Find(Pre[x]);
}
//合并
void Union(int x, int y, int &n) {
int fx = Find(x), fy = Find(y);
if (fx == fy) return;
Pre[fx] = fy;
n--;
}
int main() {
int n, m;
while (~scanf("%d", &n)) {
if (n == 0) break;
for (int i = 0; i <= n; i++) Pre[i] = i;
scanf("%d", &m);
while (m--) {
int c1, c2;
scanf("%d%d", &c1, &c2);
Union(c1, c2, n);
}
printf("%d\n", n - 1);
}
return 0;
}
最小生成樹
題目鏈接：https://www.luogu.org/problem/P3366
題解： https://www.cnblogs.com/czc1999/p/11735791.html
求連通分量個數
并查集
求連通塊數量，沒找著簡單的模板題，代碼比較容易理解，
#include <iostream>
using namespace std;
int pre[maxn];
int Find(int x) {
if (pre[x] == x)return x;
return pre[x] = Find(pre[x]);
}
void Union(int x, int y) {
int fx = Find(x), fy = Find(y);
if (fx == fy) return;
pre[fx] = fy;
}
int main(){
int m, n;
cin >> n;
for (int i = 0; i < n; i++) pre[i] = i;
cin >> m;
while (m--) {
int c1, c2;
cin >> c1 >> c2;
Union(c1, c2);//兩點之間有路的屬于同一個連通塊，合并起來
}
int cnt = 0;
for (int i = 0; i < n; i++) {
if (pre[i] == i) cnt++; //有多少個根結點，就有多少個連通塊
}
cout << cnt << endl;
return 0;
}
DFS
寫了玩的
#include <iostream>
using namespace std;
int m, n;
int cnt = 0;
int maze[500][500];
bool book[500][500];
int dir[4][2] = { {0,-1},{0,1},{-1,0},{1,0} };
void dfs(int x, int y) {
for (int i = 0; i < 4; i++) {
int tox = x + dir[i][0], toy = y + dir[i][1];
if (!book[tox][toy] && maze[tox][toy] == 1 && (tox >= 0 && tox < m && toy >= 0 && toy < n)) {
book[tox][toy] = true;
dfs(tox, toy);
}
}
return;
}
int main() {
cin >> m >> n;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
cin >> maze[i][j];
}
}
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (maze[i][j] && !book[i][j]) {
dfs(i, j);
cnt++;
}
}
}
cout << cnt;
return 0;
}
BFS
#include <iostream>
#include <stdio.h>
#include <queue>
using namespace std;
struct node {
int x;
int y;
node(int x, int y) :x(x), y(y) {};
};
queue<node> q;
int maze[105][105];
bool book[105][105];
int m, n;
int dir[4][2] = { {0,-1},{0,1},{-1,0},{1,0} };
void bfs(int x1, int y1) {
node nn;
nn.x = x1; nn.y = y1;
while (!q.empty()) q.pop();
q.push(nn);
book[x1][y1] = true;
while (q.empty() == false) {
node now = q.front();
q.pop();
for (int i = 0; i < 4; i++) {
int tox = now.x + dir[i][0];
int toy = now.y + dir[i][1];
if (!book[tox][toy] && maze[tox][toy] == 1 && (tox >= 0 && tox < m && toy >= 0 && toy < n)) {
book[tox][toy] = true;
q.push(node(tox, toy));
}
}
}
}
int main(int argc, char** argv) {
cin >> m >> n;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
cin >> maze[i][j];
}
}
int ans = 0;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (maze[i][j] && !book[i][j] ) {
bfs(i, j);
ans++;
}
}
}
cout << ans << endl;
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/128445.html
標籤：其他