Znzryb's Blog
0%

E - K-th Largest Connected Components

Posted on Edited on

题目大意

给定一个有 N 个点、初始没有边的无向图，按顺序处理 Q 个操作：

  • 操作 1：在 u 与 v 之间新增一条边。

  • 操作 2：询问与点 v 连通的所有点中，点编号第 k 大的是多少；如果连通块大小不足 k，输出 -1。（题目保证 kle10k le 10）

这题总体上来说还是不难的，就是用并查集维护连通块，再用set维护第k大的点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
//  https://atcoder.jp/contests/abc372/tasks/abc372_e
#include <iostream>
#include <vector>
#include <set>
#include <iterator>
using namespace std;
const int maxn=2e5+10;
int n,q,op,u,v,k,fa[maxn];  // fa is disjointed set to upd connected components
// vector <int> g[maxn];
set <int,greater<int> > g[maxn];
int find(int x){
    if(fa[x]!=x){
        fa[x]=find(fa[x]);
        return fa[x];
    }else{
        return x;
    }
}
void unionn(int i,int j){
    int i_fa=find(i);
    int j_fa=find(j);
    fa[j_fa]=i_fa;
    g[i_fa].insert(g[j_fa].begin(),g[j_fa].end());
    while(g[i_fa].size()>10) {
        set<int>::iterator it=g[i_fa].end();
        advance(it,-1);
        g[i_fa].erase(it);
    }
		
}
inline void query1(){
    // g[u].push_back(v);
    // g[v].push_back(u);
    unionn(u,v);
}
inline void query2(){
    int v_fa=find(v),cnt=0;bool isBreak=false;
    for(set<int>::iterator it=g[v_fa].begin();it!=g[v_fa].end();it++){
        cnt+=1;
        if(cnt==k){
            cout<<*it<<endl;isBreak=true;break;
        }
    }
    if(!isBreak)
        cout<<-1<<endl;
}
//void out(){
//	for(int i=1;i<=n;i++){
//		for(set<int>::iterator it=g[i].begin();it!=g[i].end();it++)
//			cout<<*it<<" ";
//		cout<<endl;
//	}
//}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>n>>q;
    for(int i=1;i<=n;i++) fa[i]=i,g[i].insert(i);  //initialize disjointed set.
    for(int _=1;_<=q;_++){
        cin>>op;
        if(op==1)
            cin>>u>>v,query1();
        else
            cin>>v>>k,query2();
    }
    //cout<<endl<<"set:"<<endl;
    //out();
    //cin>>n;
}
// AC*39 TLE*32 https://atcoder.jp/contests/abc372/submissions/58388612
// AC https://atcoder.jp/contests/abc372/submissions/58389524
// AC https://www.luogu.com.cn/record/179882194