ABC372：K-th Largest Connected Components（并查集启发式合并）
问题陈述
有一个无向图，图中有 NN 个顶点和 00 条边。顶点编号为 11 至 NN 。
您会收到 QQ 个查询，需要按顺序处理。每个查询都属于以下两种类型之一：
- 类型 11 ：以
1 u v格式给出。在顶点 uu 和 vv 之间添加一条边。 - 类型 22 ：格式为
2 v k.打印与顶点 vv 连接的顶点中 kk /th 最大的顶点编号。如果连接到顶点 vv 的顶点少于 kk ，则打印-1。
做法
本题就是建立集合，然后求集合中的第k大数。我们自然而然想到并查集来维护集合，而因为k很小，我们直接暴力求就好。
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
int n,q,fa[N];
int getfa(int x){
if(x==fa[x]) return x;
else return fa[x]=getfa(fa[x]);
}
void setfa(int x,int y){
fa[getfa(x)]=getfa(y);
}
int main(){
scanf("%d%d",&n,&q);
vector<set<int> > g(n+1);
for(int i=1;i<=n;i++){
g[i].insert(i);
fa[i]=i;
}
while(q--){
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
if(a==1){
int u=getfa(b),v=getfa(c);
if(u==v) continue;//不加会超时
if(u>v) swap(u,v);
for(auto x:g[u]) g[v].insert(x);
setfa(u,v);//小的集合加到大的集合里
}
else{
int u=getfa(b);
if(g[u].size()<c) cout<<-1<<endl;
else{//数据范围很小 ,可以直接暴力求
auto it=g[u].end();
while(c--) it--;
cout<<*it<<endl;
}
}
}
}wa的原因
1.合并集合的时候，没有用并查集合并两个集合。而是用vector来存每个点所连接的点，忽略了两个点代表的是两个集合，两个集合中不可能只有单单这两个点
原文地址：https://blog.csdn.net/2301_80718054/article/details/142558081
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！