abc372_E

E - K-th Largest Connected Components

思路

由于要求求所求点第\(k\)大点，所以在每个点上开一个\(set\)就可以了，因为\(k\)小于\(10\)所以直接遍历取第\(k\)大就行了，当连接两点的时候，使用并查集维护，因为要合并，但直接合并会超时，所以使用启发式合并

其中有一个重要的点就是启发式合并的时候，如果两个点相同，就直接跳过，要不然就会被卡t

代码

const int N=2e5+10;
set<int> g[N];

void solve() {
    int n,q;
    cin>>n>>q;
    // vector<set<int>> g(n+1);
    for(int i=1;i<=n;i++) g[i].insert(i);
    vector<int> p(n+1);
    for(int i=1;i<=n;i++) p[i]=i;
    auto find=[&](auto&&self,int x)->int{
        if(x!=p[x]) p[x]=self(self,p[x]);
        return p[x];
    };
    while(q--){
        int op,a,b;
        cin>>op>>a>>b;
        if(op==1){
            a=find(find,a),b=find(find,b);
            if(a==b) continue;
            if(g[a].size()<g[b].size()) swap(g[a],g[b]);                         
            for(auto tt:g[b]) g[a].insert(tt);
            p[b]=a;
        }
        else{
            int fa=find(find,a);
            // cout<<fa<<" "<<g[fa].size()<<endl;
            if(g[fa].size()<b) cout<<-1<<endl;
            else cout<<*prev(g[fa].end(),b)<<endl;
        }
    }
}