【并查集】[ABC372E] K-th Largest Connected Components 题解
题意
前置阅读：并查集算法介绍
洛谷链接
Atcoder 链接
给定 n ( 1 ≤ n ≤ 2 × 1 0 5 ) n(1 \leq n \leq 2\times 10^5) n(1≤n≤2×105) 个点，初始没有边，您要进行以下操作：
1 a b，表示连接一条 ( a , b ) (a,b) (a,b) 无向边，保证 1 ≤ a < b ≤ n 1 \leq a < b \leq n 1≤a<b≤n
2 a b，表示查询在 a a a 这个联通块中，它能去到的点的编号的第 b b b 大的点为几号（可以去到的点包括这个点本身）。若无，输出 -1。保证 1 ≤ a ≤ n , 1 ≤ b ≤ 10 1 \leq a \leq n,1 \leq b \leq 10 1≤a≤n,1≤b≤10
思路
考虑操作 2 中 b b b取值较小，用预处理的方式，记 c o n n e c t i , j connect_{i,j} connecti,j 表示在 i i i 这个联通块中第 j j 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;
}