#include <stdio.h>
#include <string.h>
#define lowbit(i) i&(-i)
#define maxn 300000
using namespace std;
int a[maxn],c[maxn],p[maxn];
int fd(int x)
{
return x==p[x] ? x :fd(p[x]);
}
void update(int x,int val)
{
while(x<=maxn)
{
c[x]+=val;
x+=lowbit(x);
}
}
int find_kth(int k)
{
int ans = 0,cur = 0;
for(int i=20;i>=0;i--)
{
ans+=(1<<i);
if(ans>maxn||cur+c[ans]>=k)
ans-=(1<<i);
else
cur+=c[ans];
}
return ans+1;
}
int main()
{
int n,m,k,l,t,q,x,y;
scanf("%d %d",&n,&m);
for(int i=1;i<=n;i++)
{
p[i]=i;
a[i]=1;
}
update(1,n);
int num = n;
while(m--)
{
scanf("%d",&q);
if(q==0)
{
scanf("%d %d",&x,&y);
x = fd(x);
y = fd(y);
if(x==y) continue;
update(a[x],-1);
update(a[y],-1);
update(a[x]+a[y],1);
p[y]=x;
a[x]+=a[y];
num--;
}
else
{
scanf("%d",&k);
printf("%d\n",find_kth(num-k+1));
}
}
return 0;
}
分享到:
相关推荐
poj2492 A Bug's Life并查集应用的扩展,希望可以给大家带来用处
NULL 博文链接:https://128kj.iteye.com/blog/1745671
NULL 博文链接:https://128kj.iteye.com/blog/1744222
POJ 1988 并查集。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。
西北工业大学POJ试题C++答案代码+课程设计
这是一道很不错的题目,即可以用线段树做也可以用树状数组,可谓经典。不过当然了线段树是比较难搞,而树状数组是极其简洁的,构造很简单,下面就分别来介绍一下两种方法...
北大POJ1207-The 3n + 1 problem 解题报告+AC代码
NULL 博文链接:https://128kj.iteye.com/blog/1744555
NULL 博文链接:https://128kj.iteye.com/blog/1747400
POJ-2870 Light Up + DFS(1级DFS+1级DFS) + Python - 思维导图 链接:https://blog.csdn.net/xxdragon126/article/details/122095922?spm=1001.2014.3001.5501
D_(POJ_1723)(思维)(第k大数).cpp
1011,1012,1013,1014,1015,1017,1026,1028,1032,1035,1041,1046,1129 1149 1154 1165 1182 1185 1190 1191 1201 1251 1273 1275 1276 1286 1322 1338 1363 1364 1401 1456 1459 1564 1579 1637 1657 1658 ...
2. bool nodePath (bstNode* pRoot, int value, std::vector*>& path) 3. { 6
并查集基础 acm 算法 poj oi 并查集基础.ppt
NULL 博文链接:https://128kj.iteye.com/blog/1746750
北大POJ初级-简单搜索 解题报告+AC代码
POJ1089 并查集可以解决 并查集加路径压缩
这份代码用C++实现了经典算法并查集,来源于poj题目1182
poj 1001答案
poj 1611 The Suspects 代码 并查集的应用