本文主要是介绍并查集题目（路径压缩、扩展域并查集、带权并查集、二维转一维并查集、逆向思维并查集），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
目录
P2814 家谱
P1955 [NOI2015] 程序自动分析
P2256 一中校运会之百米跑 （并查集结合map）
P3144 [USACO16OPEN]Closing the Farm S
P6121 [USACO16OPEN]Closing the Farm G
P1197 [JSOI2008] 星球大战
P5092 [USACO04OPEN]Cube Stacking （带权并查集）
P5877 棋盘游戏
P8686 [蓝桥杯 2019 省 A] 修改数组
P1840 Color the Axis
Supermarket
P2949 [USACO09OPEN]Work Scheduling G
P3402 可持久化并查集
P2814 家谱
#include <bits/stdc++.h>
using namespace std;
int len, cnt, father, fa[50010];
string s;
map<string, int> m;
string a[50010];
int find(int x)
{if(fa[x]==x){return x;}else return fa[x]=find(fa[x]);
}
int main()
{while(cin>>s && s[0]!='$'){string name="";len=s.length();for(int i=1; i<len; ++i){name+=s[i];}if(s[0]=='#'){if(m.count(name)!=0){father=m[name];continue;}cnt++;m[name]=cnt;a[cnt]=name;fa[cnt]=cnt;father=cnt;}else if(s[0]=='+'){if(m.count(name)!=0){int id=m[name];fa[id]=father;continue;}cnt++;m[name]=cnt;a[cnt]=name;fa[cnt]=father;}else if(s[0]=='?'){int id=m[name];cout << name << " " << a[find(id)] << endl;}}return 0;
}P1955 [NOI2015] 程序自动分析
并查集和map（哈希）结合起来的一道好题
#include <bits/stdc++.h>
using namespace std;
int t, n, fa[1000010], cnt;
bool flag;
map<int, int> m;
struct node
{int x, y, z;
}limit[1000010];
bool cmp(node a, node b)
{return a.z>b.z;
}
int find(int x)
{if(fa[x]==x){return x;}return fa[x]=find(fa[x]);
}
void merge(int u, int v)
{int fu=find(u);int fv=find(v);if(fu!=fv){fa[fu]=fv;}
}
int main()
{scanf("%d", &t);while(t--){ //10scanf("%d", &n);m.clear();flag=true;for(int i=1; i<=n; ++i){ //1e6scanf("%d %d %d", &limit[i].x, &limit[i].y, &limit[i].z);}sort(limit+1, limit+n+1, cmp); //1e6*20 for(int i=1; i<=n; ++i){ //1e6 int u=limit[i].x;int v=limit[i].y;int e=limit[i].z;if(m.count(u)==0){cnt++;fa[cnt]=cnt; //初始化并查集 m[u]=cnt; //将大范围的整数u映射成小范围的整数cnt }if(m.count(v)==0){cnt++;fa[cnt]=cnt; //初始化并查集m[v]=cnt; //将大范围的整数v映射成小范围的整数cnt }if(e==1){ //合并 merge(m[u], m[v]);} else{ //判断u和v的祖先是否相同 int fu=find(m[u]);int fv=find(m[v]);if(fu==fv){flag=false;printf("NO\n");break;}}}if(flag){printf("YES\n"); }}return 0;
}P2256 一中校运会之百米跑 （并查集结合map）
#include <bits/stdc++.h>
using namespace std;
const int N=20010;
int n, m, k, fa[N], u, v, fu, fv;
string name1, name2;
map<string, int> asd;
int find(int x)
{if(fa[x]==x){return x;}else{return fa[x]=find(fa[x]);}
}
void merge(int u, int v)
{int fu=find(u);int fv=find(v);fa[fu]=fv;
}
int main()
{scanf("%d %d", &n, &m);for(int i=1; i<=n; ++i){fa[i]=i;cin >> name1;asd[name1]=i;}while(m--){cin >> name1 >> name2;u=asd[name1];v=asd[name2];merge(u, v);}scanf("%d", &k);while(k--){cin >> name1 >> name2;u=asd[name1];v=asd[name2];if(find(u)==find(v)){printf("Yes.\n");}else{printf("No.\n");}}return 0;
}P3144 [USACO16OPEN]Closing the Farm S
并查集倒着做合并， AC
#include <bits/stdc++.h>
using namespace std;
int n, m, u, v, close[3010], fa[3010], cnt;
bool in[3010], vis[3010];
string ans[3010];
vector<int> a[3010];
int find(int x)
{if(x==fa[x]){return x;}else{return fa[x]=find(fa[x]);}
}
void merge(int u, int v)
{int fu=find(u);int fv=find(v);fa[fu]=fv;
}
int main()
{scanf("%d %d", &n, &m);while(m--){scanf("%d %d", &u, &v);a[u].push_back(v);a[v].push_back(u);}for(int i=1; i<=n; ++i){fa[i]=i;scanf("%d", &close[i]); //要关掉的谷仓编号 }for(int i=n; i>=1; --i){u=close[i];in[u]=true; //该点加入到图中for(int j=0; j<a[u].size(); ++j){v=a[u][j];if(in[v]){merge(u, v); }} memset(vis, 0, sizeof(vis));cnt=0;for(int j=1; j<=n; ++j){if(in[j] && !vis[find(j)]){vis[find(j)]=true;cnt++;if(cnt>1){break;}}}if(cnt>1){ans[i]="NO";}else{ans[i]="YES";}}for(int i=1; i<=n; ++i){cout << ans[i] << endl;}return 0;
}暴力做法，50分, TLE
#include <bits/stdc++.h>
using namespace std;
int n, m, a[3010][3010], u, v, start[3010], close, vis[3010], cnt;
queue<int> q;
bool check(int x)
{//多测清空 cnt=0;memset(vis, 0, sizeof(vis));while(!q.empty()){q.pop();}//找起点 for(int i=1; i<=n; ++i){if(start[i]==false){q.push(i);vis[i]=true;cnt=1;break; }}//遍历 while(!q.empty()){if(cnt==n-x){return true;}u=q.front();q.pop();for(int i=1; i<=n; ++i){if(a[u][i] && !vis[i]){vis[i]=true;cnt++;q.push(i);}}}return false;
}
int main()
{scanf("%d %d", &n, &m);while(m--){scanf("%d %d", &u, &v);a[u][v]=a[v][u]=1; //建边 }for(int i=1; i<=n; ++i){if(check(i-1)){ //关掉i-1个谷仓 printf("YES\n");}else{printf("NO\n");}scanf("%d", &close); //要关掉的谷仓编号 start[close]=true; //标记为关闭状态 for(int j=1; j<=n; ++j){ //断边 a[close][j]=a[j][close]=0; }}return 0;
}P6121 [USACO16OPEN]Closing the Farm G
#include <bits/stdc++.h>
using namespace std;
int n, m, u, v, close[200010], fa[200010], cntedge, cntnode;
bool in[200010], vis[200010];
string ans[200010];
vector<int> a[200010];
int find(int x)
{if(x==fa[x]){return x;}else{return fa[x]=find(fa[x]);}
}
void merge(int u, int v)
{int fu=find(u);int fv=find(v);fa[fu]=fv;
}
int main()
{scanf("%d %d", &n, &m);while(m--){scanf("%d %d", &u, &v);a[u].push_back(v);a[v].push_back(u);}for(int i=1; i<=n; ++i){fa[i]=i;scanf("%d", &close[i]); //要关掉的谷仓编号 }//O(M)for(int i=n; i>=1; --i){u=close[i];cntnode++;in[u]=true; //该点加入到图中for(int j=0; j<a[u].size(); ++j){v=a[u][j];if(in[v] && find(u)!=find(v)){merge(u, v); cntedge++;}} if(cntedge+1<cntnode){ans[i]="NO";}else{ans[i]="YES";}}for(int i=1; i<=n; ++i){cout << ans[i] << endl;}return 0;
}P1197 [JSOI2008] 星球大战
#include <bits/stdc++.h>
using namespace std;
int n, m, u, v, k, close[400010], fa[400010], cntedge, cntnode, asd;
int ans[400010];
bool in[400010], vis[400010];
vector<int> a[400010];
int find(int x)
{if(x==fa[x]){return x;}else{return fa[x]=find(fa[x]);}
}
void merge(int u, int v)
{int fu=find(u);int fv=find(v);fa[fu]=fv;
}
int main()
{scanf("%d %d", &n, &m);for(int i=0; i<n; ++i){fa[i]=i;}while(m--){scanf("%d %d", &u, &v);a[u].push_back(v);a[v].push_back(u);}scanf("%d", &k); for(int i=1; i<=k; ++i){scanf("%d", &close[i]); //要关掉的星球编号vis[close[i]]=true; //如果某个星球始终没有被关掉, 则vis为false }asd=n-k; //假设这些点都没相连, 联通块数量最多为n-k //逆向思维处理, 反向建设相当于正向摧毁 //先处理k座星球全部被摧毁后的情况 for(int i=0; i<n; ++i){if(!vis[i]){ //i始终没有被摧毁 in[i]=true; //i在图里 for(int j=0; j<a[i].size(); ++j){ v=a[i][j]; //枚举与i相连的点 if(!vis[v] && find(i)!=find(v)){ //如果该点也始终没有被摧毁, 并且有边相连 merge(i, v); //合并 asd--; //联通块数量减一 }}}}ans[k+1]=asd;//再逆向处理第i座星球被摧毁前的情况for(int i=k; i>=1; --i){//把第i座星球加入到图中 u=close[i];asd++;in[u]=true; //该点加入到图中for(int j=0; j<a[u].size(); ++j){v=a[u][j];if(in[v] && find(u)!=find(v)){ //连一条边, 没有形成环 merge(u, v); //合并 asd--; //联通块数量-- }} ans[i]=asd;}for(int i=1; i<=k+1; ++i){cout << ans[i] << endl;}return 0;
}P5092 [USACO04OPEN]Cube Stacking （带权并查集）
#include <bits/stdc++.h>
using namespace std;
const int N=30010;
int p, fa[N], dis[N], size[N], u, v;
char opt;
int find(int x)
{if(fa[x]==x){return x;}int root=find(fa[x]); //找到自己祖宗结点的祖宗 dis[x]+=dis[fa[x]]; //更新到自己祖宗的祖宗(root)的距离, 等于自己到当前祖宗结点的距离+当前祖宗结点到它的祖宗结点的距离 return fa[x]=root; //直接链到最终的祖宗
}
void merge(int u, int v)
{int fu, fv; fu=find(u);fv=find(v);if(fu==fv) return;fa[fu]=fv;dis[fu]+=size[fv]; //距离先存在祖宗结点fu这里, 后面需要用的时候find去更新 size[fv]+=size[fu]; //祖宗保存元素个数
}
int main()
{scanf("%d", &p);for(int i=1; i<=N; ++i){ //并查集初始化, dis[i]默认为0 fa[i]=i; size[i]=1;}while(p--){cin >> opt;if(opt=='M'){ //将包含 u 的立方柱移动到包含 v 的立方柱上scanf("%d %d", &u, &v); merge(u, v); }else if(opt=='C'){ //统计含 u 的立方柱中，在 u 下方的方块数目。scanf("%d", &u);find(u);printf("%d\n", dis[u]);}}return 0;
}P5877 棋盘游戏
二维转一维，用并查集处理
#include <bits/stdc++.h>
using namespace std;
int n, m, c, x, y, a[510][510], fa[250010], id, asd;
int mx[5]={0, -1, 1, 0, 0};
int my[5]={0, 0, 0, -1, 1};
int find(int x)
{if(fa[x]==x){return x;}else{return fa[x]=find(fa[x]);}
}
void merge(int u, int v)
{int fu=find(u);int fv=find(v);fa[fu]=fv;
}
int main()
{scanf("%d %d", &n, &m);for(int i=1; i<=n; ++i){for(int j=1; j<=n; ++j){id=(i-1)*n+j;fa[id]=id;}}memset(a, -1, sizeof(a));while(m--){scanf("%d %d %d", &c, &x, &y);asd++;id=(x-1)*n+y;a[x][y]=c;for(int i=1; i<=4; ++i){int nx=x+mx[i];int ny=y+my[i];if(nx>=1 && nx<=n && ny>=1 && ny<=n && a[nx][ny]==c && find(id)!=find((nx-1)*n+ny)){merge(id, (nx-1)*n+ny);asd--;}}printf("%d\n", asd);}return 0;
}P8686 [蓝桥杯 2019 省 A] 修改数组
路径压缩，删除中间的数，相当于区间合并
#include <bits/stdc++.h>
using namespace std;
int n, fa[2000010], a[100010];
bool vis[2000010];
int find(int x)
{if(fa[x]==x){return x;} else{return fa[x]=find(fa[x]);}
}
void merge(int u, int v)
{int fu=find(u);int fv=find(v);fa[fu]=fv;
}
int main()
{scanf("%d", &n);for(int i=1; i<=2000000; ++i){fa[i]=i;}for(int i=1; i<=n; ++i){scanf("%d", &a[i]);}for(int i=1; i<=n; ++i){if(find(a[i])==a[i]){ //没出现 cout << a[i] << " ";merge(a[i], a[i]+1);}else{ //出现过 cout << fa[a[i]] << " ";merge(fa[a[i]], fa[a[i]]+1);}}return 0;
}P1840 Color the Axis
并查集进行区间合并
#include <bits/stdc++.h>
using namespace std;
int n, m, fa[200010], l, r, asd;
int find(int x)
{if(x==fa[x]){return x;}else{return fa[x]=find(fa[x]);}
}
void merge(int u, int v)
{int fu=find(u);int fv=find(v);//让大的当父亲, 不然会TLE fa[fu]=fv;
}
int main()
{scanf("%d %d", &n, &m);asd=n;//注意细节, 需要初始化到n+1, 不然TLE for(int i=1; i<=n+1; ++i){fa[i]=i;} while(m--){scanf("%d %d", &l, &r);for(int i=l; i<=r; i=find(i)){//如果该点没有被涂过 if(find(i)==i){ asd--; //答案-- //该点被涂过了, 将该点和下一个点合并,//当下次再找到该点时, 直接通过find(i)跳到下一个没有被涂的点 merge(i, i+1); } }printf("%d\n", asd); }return 0;
}Supermarket
Supermarket - 洛谷
P2835 刻录光盘
P1333 瑞瑞的木棍
P2391 白雪皑皑
P2949 [USACO09OPEN]Work Scheduling G
P3402 可持久化并查集
这篇关于并查集题目（路径压缩、扩展域并查集、带权并查集、二维转一维并查集、逆向思维并查集）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
