文章目錄

• 并查集
• • • 只需要尋找到根節(jié)點，判斷是否在同一集合內(nèi)
    • 記錄連通塊中點的個數(shù)
    • 找到根節(jié)點并且記錄到根結(jié)點的距離
    • 并查集+01背包問題
    • 并查集+離散化
    • • 離散化

并查集

并查集相關(guān)基礎(chǔ)知識

只需要尋找到根節(jié)點，判斷是否在同一集合內(nèi)

//p[i]表示i結(jié)點的根節(jié)點
int find(int n){
if(p[n]!=n)p[n]=find(p[n]);
return p[n];
}

集合合并

#include<bits/stdc++.h>using namespace std;
const int N=100010;
int p[N];
int  find(int x){if(p[x]!=x)p[x]=find(p[x]);return p[x];
}int main(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);int n,m;cin>>n>>m;for(int i=1;i<=n;i++)p[i]=i;while(m--){char ch;int a,b;cin>>ch>>a>>b;if(ch=='M'){if(p[a]!=p[b])p[find(a)]=find(b);//b為根結(jié)點}else{if(find(a)==find(b))puts("Yes");else puts("No");}}return 0;
}

記錄連通塊中點的個數(shù)

連通塊中點的個數(shù)

#include<bits/stdc++.h>using namespace std;const int N=100010;
int p[N],s[N];
int n,k;int find(int n){if(p[n]!=n)p[n]=find(p[n]);return p[n];
}int main(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);
cin>>n>>k;
for(int i=1;i<=n;i++)p[i]=i,s[i]=1;while(k--){string ch;cin>>ch;if(ch=="C"){int a,b;cin>>a>>b;a=find(a),b=find(b);if(a!=b){p[a]=b;s[b]+=s[a];//b的根結(jié)點的點的數(shù)量+a的根結(jié)點的點的數(shù)量}}else if(ch=="Q1"){int a,b;cin>>a>>b;if(find(a)==find(b))cout<<"Yes"<<endl;else cout<<"No"<<endl;}else if(ch=="Q2"){int a;cin>>a;cout<<s[find(a)]<<endl;}}return 0;
}

找到根節(jié)點并且記錄到根結(jié)點的距離

//b[i]表示i結(jié)點到根結(jié)點的距離
int find(int n){
if(p[n!=n]){
int t=find(p[n]);
d[n]+=d[p[n]];
p[n]=t;
}
return p[n];}

食物鏈

#include<bits/stdc++.h>using namespace std;const int N = 150010;
int p[N], cnt=0, d[N];
int n, k;
int find(int n) {if (p[n] != n) {int tmp = find(p[n]);d[n] += d[p[n]];p[n] = tmp;}return p[n];
}int main() {cin >> n >> k;for (int i = 1; i <= n; i++)p[i] = i;while (k--) {int s, a, b;cin >> s >> a >> b;int sa = find(a), sb = find(b);if (a > n || b > n) {cnt++;continue;}else {if (s == 1) {if (sa == sb && (d[a] - d[b]) % 3)cnt++;else if (sa != sb) {p[sa] = sb;d[sa] = d[b] - d[a];//(d[a]+d[sa]-d[b])%3==0;mod 3省略}}else {if (sa == sb && (d[a] - d[b] - 1) % 3)cnt++;else if (sa != sb) {p[sa] = sb;d[sa] = d[b] - d[a] + 1;}}}}cout << cnt;return 0;
}

格子游戲

#include<bits/stdc++.h>
using namespace std;const int N = 40010;
int n, m;
int p[N];int find(int n) {if (p[n] != n)p[n] = find(p[n]);return p[n];
}int main() {cin >> n >> m;int res = 0;for (int i = 0; i < n * n; i++)p[i] = i;for (int i = 1; i <= m; i++) {int a, b;char ch;cin >> a >> b >> ch;a--, b--;int sa = a * n + b;if (ch == 'D') {if (find(sa) == find(sa + n)) {res = i;break;}else p[sa + n] = p[sa];}else if (ch == 'R') {if (find(sa) == find(sa + 1)) {res = i;break;}else p[sa + 1] = p[sa];}}if (res == 0)cout << "draw";else cout << res;return 0;
}

并查集+01背包問題

搭配購買
將所有的當(dāng)前集合內(nèi)的子節(jié)點的V和W都累加到根節(jié)點上。

#include<bits/stdc++.h>using namespace std;const int N = 10010;
int p[N], v[N], w[N], f[N];int n, m, q;
int find(int n) {if (p[n] != n)p[n] = find(p[n]);return p[n];
}int main() {cin >> n >> m >> q;for (int i = 1; i <= n; i++)p[i] = i;for (int i = 1; i <= n; i++)cin >> v[i] >> w[i];for (int i = 1; i <= m; i++) {int a, b;cin >> a >> b;int sa = find(a), sb = find(b);if (sa != sb) {v[sb] += v[sa];w[sb] += w[sa];p[sa] = p[sb];}}for (int i = 1; i <= n; i++)if (p[i] == i)for (int j = q; j >= v[i]; j--)f[j] = max(f[j], f[j - v[i]] + w[i]);cout << f[q];return 0;
}

并查集+離散化

離散化

離散化就是將稀疏的數(shù)通過映射壓縮到容器中，減少不需要的遍歷而縮短時間

離散化求區(qū)間和

本題解釋

#include<bits/stdc++.h>using namespace std;const int N=300010;
int a[N],s[N];typedef pair<int ,int>PII;
vector<int>alls;
vector<PII>add,query;int find(int n){int l=0,r=alls.size()-1;while(l<r){int mid=l+r >>1;if(alls[mid]>=n)r=mid;else l=mid+1;}return r+1;
}int main(){int n,m;cin>>n>>m;for(int i=0;i<n;i++){int a,b;cin>>a>>b;add.push_back({a,b});alls.push_back(a);}for(int i=0;i<m;i++){int x,y;cin>>x>>y;query.push_back({x,y});alls.push_back(x);alls.push_back(y);}sort(alls.begin(),alls.end());alls.erase(unique(alls.begin(),alls.end()),alls.end());for(auto item:add){int x=find(item.first);a[x]+=item.second;}for(int i=1;i<=alls.size();i++)s[i]=s[i-1]+a[i];for(auto item:query){int l=find(item.first),r=find(item.second);cout<<s[r]-s[l-1]<<endl;}return 0;}

程序自動分析
這題離散化不需要保序。。。

#include<bits/stdc++.h>
using namespace std;
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<unordered_map>
#include<iostream>
const int N = 2000010;
int n, m;
int p[N];
unordered_map<int, int>S;
struct Query {int x, y, e;
}query[N];
int get(int x) {if (S.count(x) == 0)S[x] = ++n;return S[x];
}
int find(int x) {if (p[x] != x)p[x] = find(p[x]);return p[x];
}
int main() {ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);int T;cin >> T;while (T--) {n = 0;S.clear();cin >> m;for (int i = 0; i < m; i++) {int x, y, e;cin >> x >> y >> e;query[i] = { get(x),get(y),e };}for (int i = 1; i <= n; i++)p[i] = i;//合并所有相等約束條件for (int i = 0; i < m; i++) {if (query[i].e == 1) {int pa = find(query[i].x), pb = find(query[i].y);p[pa] = pb;}}//檢查所有不等條件bool has_confict = false;for(int i=0;i<m;i++)if (query[i].e == 0) {int pa = find(query[i].x), pb = find(query[i].y);if (pa == pb) {has_confict = true;break;		}	}if (has_confict)puts("NO");else puts("YES");}return 0;
}

總結(jié)

以上是生活随笔為你收集整理的并 查 集的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。