并查集簡介
并查集的兩類操作：
- Get 查詢任意一個元素是屬于哪一個集合，
- Merge 把兩個集合合并在一起，
基本思想：找到代表元，
注意有兩種方法：
-
使用一個固定的值（查詢方便，但是在合并的時候需要修改大量的值，比較復雜）
-
使用樹形結構，這樣合并的時候可以直接讓一個叫另一個
eg.
f[root1] = root2
并查集的路徑壓縮以及按秩合并
路徑壓縮：在每一次進行合并的時候，順便更改每一個節點的值，（均攤復雜度：\(O(logN)\)）
按秩合并：每一次查詢的均攤復雜度是\(O(logN)\)，
如果兩個一起使用，那么最終的復雜度是線性的，但是正常使用路徑壓縮就行，
使用并查集來維護具傳遞性的性質
僅僅維護具有傳遞性：
AcWing237. 程式自動分析
思路：
- 一種方法是使用樹的無向圖來進行維護相等關系，（每一個塊里面全部相等）
- 再就是使用并查集來維護傳遞關系，
- 注意：相等具有傳遞性，但是不相等不具備傳遞性，
代碼：
#include <bits/stdc++.h>
using namespace std;
int fa[200010];
map<int , int >mp;
vector<pair<int, int> >v;
int get(int x)
{
if(fa[x] == x) return x;
return fa[x] = get(fa[x]);
}
void solve(int n)
{
bool tag = true;
v.clear();
int cnt = 0;
for(int i = 1; i <= 2*n; i++) fa[i] = i;
mp.clear();
int a, b, eq;
for(int i = 1; i <= n; i++)
{
scanf("%d%d%d", &a, &b, &eq);
if(mp.find(a) == mp.end()) mp[a] = ++cnt;
if(mp.find(b) == mp.end()) mp[b] = ++cnt;
if(eq == 0)
{
v.push_back(make_pair(mp[a], mp[b]));
}
else
{
fa[get(mp[a])] = get(mp[b]);
}
}
for(vector<pair<int, int > >::iterator it = v.begin(); it != v.end(); it++)
{
pair<int, int>t = *it;
if(get(t.first) == get(t.second))
{
tag = false;
break;
}
}
//for(int i = 1; i <= 2*n; i++)
//{
// printf("%d\t%d", i, fa[])
//}
if(tag) puts("YES");
else puts("NO");
}
int main()
{
int T;
cin >> T;
while(T--)
{
int n;
scanf("%d", &n);
solve(n);
}
return 0;
}
并查集的帶權路徑以及擴展域：
- 可以在logN的復雜度內查詢某一個節點（在“鏈”中）到根節點的距離
- 但是也具有要求
在合并的時候，必須是把一個集合全部按照原有的順序合并到另一個集合的末尾，
這個時候，有兩個陣列 d 和 size 集合：
- 如果是根節點，那么就size里存有這一個集合元素的多少，
- 其他節點存放到父親節點的帶權路徑長度d，
注意：僅僅在查詢過后，d陣列的內容才是到根節點的距離，
AcWing238. 銀河英雄傳說
代碼
#include <bits/stdc++.h>
using namespace std;
int fa[30010];
int d[30010];
int s[30010];
int get(int x)
{
if(x == fa[x]) return x;
int root = get(fa[x]);
d[x] += d[fa[x]];
fa[x] = root;
return root;
}
int merge(int a, int b)
{
int x = get(a);
int y = get(b);
fa[x] = y;
d[x] = s[y];
s[y] += s[x];
}
int main()
{
int T;
cin >> T;
for(int i = 0; i <= 30002; i++)
{
fa[i] = i;
d[i] = 0;
s[i] = 1;
}
while(T--)
{
char buf[12];
int a, b;
scanf("%s%d%d", buf, &a, &b);
if(buf[0]=='M')
{
if(get(a) != get(b))//如果在一次合并之后，再次合并，那么就是把一個空的合并到了戰艦末尾，
merge(a, b);
}
else
{
int x = get(a);
int y = get(b);
if(x==y)
{
if (a==b) puts("0");//注意可能兩次詢問的是同一個戰艦
else printf("%d\n", abs(d[a]-d[b])-1);
}
else
puts("-1");
}
}
return 0;
}
239. 奇偶游戲
思路：
這道題目涉及到區間內的操作，
需要把區間的操作轉化為端點的操作，
不妨假設有一個前綴陣列，保存著從最開始的點到這一個位置1的個數，
現在進行一下轉化：
- 如果一個區間內有奇數個1，那么端點的奇偶性不同，
- 如果一個區間內有偶數個1，那么端點奇偶性相同，
維護一種傳遞的關系： 使用并查集
注意：區間長度大，但是總體數目少，可以考慮離散化，
方法一：采用帶邊權來進行實作，
與上一題不同，對于一個抽象的并查集，把一個合并到另一個上時，邊權是可以自己給定的，
淺淺地證明一下：當區間端點沒有發生沖突，那么存在一種序列滿足條件
（為了說明區間端點的沖突是造成判斷說謊的充分必要條件）
#include <bits/stdc++.h>
using namespace std;
map<int , int> mp;
int fa[10010];
int d[10010];
//int s[10010];
int get(int x)
{
if(x == fa[x]) return x;
int root = get(fa[x]);
d[x] = d[fa[x]] ^ d[x];
return fa[x] = root;
}
bool merge(int a, int b, int mod)
{
int x = get(a);
int y = get(b);
if(x==y)
{
if(d[a] ^ d[b] == mod)
return true;
else
return false;
}
fa[x] = y;
d[x] = mod^d[a]^d[b];
return true;
}
int main()
{
for(int i = 0; i <= 10000; i++)
{
fa[i] = i;
d[i] = 0;
}
int ans = INT_MAX;
int cnt = 0;
int N, M;
cin >> N >> M;
for(int i = 1; i <= M; i++)
{
int a, b;
char buf[12];
scanf("%d%d%s", &a, &b, buf);
a--;
if(mp.find(a) == mp.end()) mp[a] = ++cnt;
if(mp.find(b) == mp.end()) mp[b] = ++cnt;
bool tag;
if(buf[0] == 'e')
tag = merge(mp[a], mp[b], 0);
else
tag = merge(mp[a], mp[b], 1);
if(!tag)
{
ans = min(ans, i);
}
}
if(ans == INT_MAX)
printf("%d\n", M);
else
printf("%d", ans-1);
return 0;
}
方法二：采用拓展域來進行求解：
還是有一種等價關系，只不過可能由這一個域推到另一個域上，所以，采用多個域來維護傳遞性，
思路
如果進行查詢，沒有發現矛盾，直接合并（因為如果本來在一起，合并也沒有什么后果）
代碼
#include <bits/stdc++.h>
using namespace std;
map<int , int> mp;
int fa[20010];
const int divv = 10002;
int get(int x)
{
if(x== fa[x]) return x;
return fa[x] = get(fa[x]);
}
bool merge(int x, int y, int mod)
{
int x_odd = x;
int x_even = x + divv;
int y_odd = y;
int y_even = y + divv;
if(mod)//奇數
{
if(get(x_odd) == get(y_odd))
{
return false;
}
else
{
fa[get(x_odd)] = get(y_even);
fa[get(y_odd)] = get(x_even);
}
}
else
{
if(get(x_odd) == get(y_even))
return false;
else
{
fa[get(x_odd)] = get(y_odd);
fa[get(x_even)] = get(y_even);
}
}
return true;
}
int main()
{
for(int i = 0; i <= 20009; i++)
{
fa[i] = i;
}
int ans = INT_MAX;
int cnt = 0;
int N, M;
cin >> N >> M;
for(int i = 1; i <= M; i++)
{
int a, b;
char buf[12];
scanf("%d%d%s", &a, &b, buf);
a--;
if(mp.find(a) == mp.end()) mp[a] = ++cnt;
if(mp.find(b) == mp.end()) mp[b] = ++cnt;
bool tag;
if(buf[0] == 'e')
tag = merge(mp[a], mp[b], 0);
else
tag = merge(mp[a], mp[b], 1);
if(!tag)
{
ans = min(ans, i);
}
}
if(ans == INT_MAX)
printf("%d\n", M);
else
printf("%d", ans-1);
return 0;
}
AcWing240. 食物鏈
思路：這道題目是要動態地維護傳遞關系，所以考慮到并查集，
對于這個關系來說，看不出來傳遞性，所以要使用擴展域或者是邊帶權，
方法一：擴展域
#include <bits/stdc++.h>
using namespace std;
int fa[150012];
const int divv = 50000;
int get(int x)
{
if(x == fa[x]) return x;
return fa[x] = get(fa[x]);
}
bool merge(int tag, int a, int b)
{
int a1 = a, a2 = a+divv, a3 = a2+divv;
int b1 = b, b2 = b+divv, b3 = b2 + divv;
if(tag==1)//表示a與b是同類
{
if(get(a1)==get(b2) || get(b1)==get(a2))
return false;
fa[get(a1)] = get(b1);
fa[get(a2)] = get(b2);
fa[get(a3)] = get(b3);
}
else//表示a吃b
{
if(get(a1)==get(b1) || get(b1) == get(a2))
return false;
fa[get(a1)] = get(b2);
fa[get(a2)] = get(b3);
fa[get(a3)] = get(b1);
}
return true;
}
int main()
{
for(int i = 1; i <= 150010; i++)
{
fa[i] = i;
}
int cnt = 0;
bool right = true;
int T, K;
cin >> T >> K;
for(int i = 1; i <= K; i++)
{
int tag, a, b;
scanf("%d%d%d", &tag, &a, &b);
if(a > T || b > T) //針對第二條判斷真偽
{
cnt ++;
right = false;
}
else if(!merge(tag, a, b))//注意：這個必須是else，因為如果
//上面一旦不合法，那么就不能進行下面的操作
{
cnt++;
right = false;
}
}
printf("%d\n", cnt);
return 0;
}
本文來自博客園，作者：心堅石穿，轉載請注明原文鏈接：https://www.cnblogs.com/xjsc01/p/16454994.html
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/498628.html
標籤：其他
上一篇：leetcode 53. Maximum Subarray 最大子陣列和(中等)
下一篇：ArrayList原始碼深度剖析，從最基本的擴容原理，到魔幻的迭代器和fast-fail機制，你想要的這都有！！！