并查集普及【模板】并查集 - 洛谷
#include<iostream>
#include<cstring>
#include<queue>
#include<vector>
#include<algorithm>
using namespace std;
#define int long long
typedef pair<int,int> PII;
#define xx first
#define yy second
const int N=1e5+10;
int n,m,w;
int p[N];
int find(int x){if(p[x]!=x)p[x]=find(p[x]);return p[x];
}
signed main(){ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);cin>>n>>m;for(int i=1;i<N;i++){p[i]=i;}while(m--){int a,b,op;cin>>op;cin>>a>>b;if(op==1){p[find(a)]=find(b);}else {if(find(a)==find(b))puts("Y");else puts("N");}}
}并查集的运用搭配购买 - 洛谷
问题分析：
这个问题其实是一个背包问题的进阶版，但是因为做题的过程中使用了并查集的算法，所以也归为并查集的进阶，对于这只能够题目来说，咱们只要看到了表示买第 ui 朵云就必须买第 vi 朵云,同理，如果买第 vi 朵就必须买第 ui 朵。这种你中带我，我中带你的感觉就是并查集的使用了。
细节就不多说了，以后的文章不会在这种细节大意都知道的地方解说。
代码的实现：
#include<iostream>
#include<cstring>
#include<queue>
#include<vector>
#include<algorithm>
using namespace std;
#define int long long
typedef pair<int,int> PII;
#define xx first
#define yy second
const int N=1e5+10;
int p[N];
struct op{int c,d;
}f[N];
int find(int x ){if(p[x]!=x)p[x]=find(p[x]);return p[x];
}
int n,m,w;
vector<PII> bag;
int dp[N];
signed main(){ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);cin>>n>>m>>w;int res=0;for(int i=1;i<N;i++)p[i]=i;for(int i=1;i<=n;i++){cin>>f[i].c>>f[i].d;}while(m--){int a,b;cin>>a>>b;p[find(a)]=find(b);} for(int i=1;i<=n;i++){if(p[i]!=i){f[find(i)].c+=f[i].c;f[find(i)].d+=f[i].d;}}for(int i=1;i<=n;i++){if(p[i]==i)bag.push_back({f[i].c,f[i].d});}for(auto i:bag){for(int j=w;j>=i.first;j--){dp[j]=max(dp[j],dp[j-i.first]+i.second);}}cout<<dp[w]<<endl;
}例题：[NOI2015] 程序自动分析 - 洛谷
代码实现：
#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <map>
#include <cmath>
#include <vector>
#include <numeric>
#include <unordered_map>
#include <queue>
#include <set>
using namespace std;
typedef pair<int,int> PII;
const int N=5e5+10;
int p[N];
int e,i,j,T,n,idx;
vector<PII> v1,v0;
unordered_map<int,int> mp;
int Get(int x){//这一步是干啥的if(!mp.count(x))mp[x]=++idx;return mp[x];
}
int find(int x){if(p[x]!=x)p[x]=find(p[x]);return p[x];
}
signed main(){cin>>T;while(T--){cin>>n;//initidx=0;for(int i=1;i<N;i++){p[i]=i;}v1.clear();v0.clear();mp.clear();while(n--){cin>>i>>j>>e;i=Get(i);j=Get(j);if(e==1){v1.push_back({i,j});}else {v0.push_back({i,j});}}for(auto it:v1){int a=find(it.first);int b=find(it.second);if(a!=b)p[a]=b;}bool flag=true;for(auto it:v0){int a=find(it.first);int b=find(it.second);if(a==b){flag=false;break;}}if(flag)puts("YES");else puts("NO");}
}以上就是有关于并查集的题目啦
