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）！