【并查集】[ABC372E] K-th Largest Connected Components 题解

题意

前置阅读：并查集算法介绍

洛谷链接

Atcoder 链接

给定 $n(1\le n\le 2\times 10^5)$ 个点，初始没有边，您要进行以下操作：

1 a b，表示连接一条 $(a,b)$ 无向边，保证 $1\le a<b\le n$

2 a b，表示查询在 $a$ 这个联通块中，它能去到的点的编号的第 $b$ 大的点为几号（可以去到的点包括这个点本身）。若无，输出 -1。保证 $1\le a\le n,1\le b\le 10$

思路

考虑操作 2 中 $b$取值较小，用预处理的方式，记 $connec{t}_{i,j}$ 表示在 $i$ 这个联通块中第 $j$大的编号，维护合并即可。代码中 count 无法正常运行，用 define 替换即可。

代码

#include<bits/stdc++.h>
#define count coount
#define int long long
using namespace std;
int q,head[200005],n;
int connect[200005][21];
int count[200005];
int find(int x) {return head[x] == x?x:head[x] = find(head[x]);
} 
int a[25];
bool cmp(int x,int y) {return x > y;
}
void hebing(int x,int y) {int cnt = 1;for(;cnt <= count[x];cnt++) {a[cnt] = connect[x][cnt];}for(;cnt <= count[x] + count[y];cnt++) a[cnt] = connect[y][cnt - count[x]];cnt--;//printf("________%lld %lld %lld\n",count[x],count[y],cnt);sort(a + 1,a + cnt + 1,cmp);for(int i = 1;i <= 10 and i <= cnt;i++) connect[x][i] = a[i];return;
}
signed main() {scanf("%lld %lld",&n,&q);for(int i = 1;i <= n;i++) count[i] = 1,connect[i][1] = i,head[i] = i;while(q--) {int a,b,c;scanf("%lld %lld %lld",&a,&b,&c);if(a == 1) {b = find(b),c = find(c);if(b != c) {hebing(b,c);count[b] += count[c];if(count[b] > 10) count[b] = 10;head[c] = b;}}else {if(count[find(b)] < c) printf("-1\n");else printf("%lld\n",connect[find(b)][c]);}}return 0;
}