当前位置：首页 > news >正文

【并查集】专题练习

news 来源：原创 2024/9/28 16:38:50

题目列表 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

模板

836. 合并集合 - AcWing题库

#include<bits/stdc++.h>
using ll=long long;
//#define int ll
const int N=1e5+10,mod=1e9+7;
int n,m;
int p[N],sz[N];
int find(int a)
{if(p[a]!=a) p[a]=find(p[a]);return p[a];
}
void merge(int a,int b)
{int pa=find(a),pb=find(b);if(pa!=pb){p[pa]=pb;sz[pb]+=sz[pa];}
}
void que(int a,int b){if(find(a)==find(b)) std::cout<<"Yes"<<'\n';else std::cout<<"No"<<'\n';
}
void solve()
{std::cin>>n>>m;for(int i=1;i<=n;i++){sz[i]=1;p[i]=i;}while(m--){char op;int a,b;std::cin>>op>>a>>b;if(op=='M'){merge(a,b);}else{que(a,b);}}}
signed main()
{std::ios::sync_with_stdio(false);std::cin.tie(0);int t=1;//std::cin>>t;while(t--){solve();}return 0;
}

837. 连通块中点的数量 - AcWing题库

#include<bits/stdc++.h>
const int N=1e5+10;
int p[N];
int size[N];
int find(int x)
{if(x!=p[x]){p[x]=find(p[x]);}return p[x];
}
void merge(int a,int b)
{int pa=find(a),pb=find(b);if(pa!=pb){p[pa]=pb;size[pb]+=size[pa];}
}
void query(int a,int b)
{int pa=find(a),pb=find(b);if(pa==pb){std::cout<<"Yes"<<'\n';}else std::cout<<"No"<<'\n';
}
void solve()
{int n,m;std::cin>>n>>m;for(int i=1;i<=n;i++){p[i]=i;size[i]=1;}while(m--){char op[5];std::cin>>op;int a,b;if(op[0]=='C') {std::cin>>a>>b;merge(a,b);}else if(op[1]=='1'){std::cin>>a>>b;query(a,b);}else{std::cin>>a;//询问a中连通块点的个数std::cout<<size[find(a)]<<'\n';}}
}
signed main()
{int t=1;//std::cin>>t;while(t--){solve();}return 0;
}

240. 食物链 - AcWing题库

普及-

（合并集合）（P2256 一中校运会之百米跑 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

判断点是否在一个集合中。

#include<bits/stdc++.h>using ll=long long;
using ull=unsigned long long;#define fir first
#define sec second
#define int llconst int N=2e4+10;
const int mod=1e9+7;
const double eps=1e-6;
int n,m;
int p[N],sz[N];
ll find(int a)
{if(p[a]!=a) p[a]=find(p[a]);return p[a];
}
void merge(int a,int b)
{int pa=find(a),pb=find(b);if(pa!=pb){p[pa]=pb;sz[pb]+=sz[pa];}
}
bool que(int a,int b)
{if(find(a)==find(b)) return true;else return false;
}
void solve()
{std::cin>>n>>m;std::map<std::string,int> mp;for(int i=1;i<=n;i++){std::string s;std::cin>>s;mp[s]=i;p[i]=i,sz[i]=1; }	for(int i=1;i<=m;i++){std::string a,b;std::cin>>a>>b;merge(mp[a],mp[b]);}int k;std::cin>>k;while(k--){std::string a,b;std::cin>>a>>b;if(que(mp[a],mp[b])) std::cout<<"Yes.\n";else std::cout<<"No.\n";}
}
signed main()
{std::ios::sync_with_stdio(false);std::cin.tie(0);int t=1;//std::cin>>t;while(t--){solve();}return 0;
}

（合并集合）P8396 [CCC2022 S2] Good Groups - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

还是个模板题

#include<bits/stdc++.h>
using ll=long long;
using ull=unsigned long long;
#define fir first
#define sec second
//#define int llconst int N=1e5+10;
const int mod=1e9+7;int n;
ll ans;
struct node{std::string s1,s2; 
}a[N];
struct nod{std::string s1,s2; 
}b[N];
std::unordered_map<std::string,std::string> p;std::string find(std::string& s)
{if(p[s]!=s) p[s]=find(p[s]);return p[s];
}
void merge(std::string& a,std::string& b)
{std::string pa=find(a),pb=find(b);if(pa!=pb){p[pa]=pb;}
}
bool que(std::string& a,std::string& b)
{if(find(a)!=find(b)) return false;else return true;
}
void solve()
{int x;//每个组3个人std::cin>>x;
//	getchar();for(int i=1;i<=x;i++){//getchar();std::cin>>a[i].s1>>a[i].s2;}int y;std::cin>>y; for(int i=1;i<=y;i++){//getchar();std::cin>>b[i].s1>>b[i].s2;}int g;std::cin>>g;for(int i=1;i<=g;i++){std::string a,b,c;//getchar();std::cin>>a>>b>>c;if(p.count(a)==0) p[a]=a;if(p.count(b)==0) p[b]=b;if(p.count(c)==0) p[c]=c;merge(a,b);merge(c,b);}ll ans=0;for(int i=1;i<=x;i++){if(!que(a[i].s1,a[i].s2)) ans++; }for(int i=1;i<=y;i++){if(que(b[i].s1,b[i].s2)) ans++; }std::cout<<ans<<'\n';
}
signed main()
{//freopen("a","w",stdout);//把结果输出到a.in里面 std::ios::sync_with_stdio(false);std::cin.tie(0);int t=1;//std::cin>>t;while(t--){solve();}return 0;
}