E - K-th Largest Connected Components 题解

__S08577__ · 2024-09-24 12:59:42 · 题解

思路

首先，该题有求联通块，不妨使用并查集求两点是否在同一联通块并且进行合并操作。 2 操作是求联通块内第 k 大，我们可以使用set来操作，合并时进行启发式合并，求第 k 大可以直接暴力求解。

代码

int find(int x){
    return fa[x]==x?x:fa[x]=find(fa[x]);
}

void merge(int u,int v){
    u=find(u),v=find(v);
    if(u!=v){
        if(s[u].size()<s[v].size()){
            for(auto i:s[u]) s[v].insert(i);
        }
        else{
            for(auto i:s[v]) s[u].insert(i);
            swap(s[u],s[v]);
        }
        fa[u]=v;
    }
}

int query(int u,int k){
    u=find(u);
    if(s[u].size()<k) return -1;
    else{
        set<int> :: iterator it;
        for(it=s[u].begin();it!=s[u].end();it++){
            k--;
            if(k==0) return *it;
        }
    }
}