题解：P8519 [IOI 2021] 钥匙

· · 题解

直接对于每个点做是 O(n(n+m)) 的。但是本题不要求我们求出所有可达性，只要求我们求出可达点最少的出发点，所以我们考虑一些合并的操作。具体来说，如果存在 u\to v，那么其实 u 就没有用了（u 肯定不优于 v），我们就可以将 u,v 合并。进行若干这种操作之后会形成若干联通块，考虑在合并上述 (u,v) 的时候，在并查集内部用 fa_i\gets v，这样子对于联通块的根节点，我们必然保存的是这个联通块内可达点最少的点。

每次只从联通块内的这个根节点向外扩展，然后合并联通块（如果一个联通块找不到其他联通块了，我们就在以后不对于它进行操作了），可以做到类似于 Boruvka 的时间复杂度。最终对于每个联通块都有一个可能成为答案的点，这个点在这个联通块之内的肯定是最优的，已知联通块的根节点 c，对于联通块内的任意一个点 u，必然可以从 u 到达 c，如果 u 也可以到达 c，那么说明 u 和 c 等价，这个时候 u 和 c 都是这个联通块的最优点。在全局取最优的一些点即可。

时间复杂度 O((n+m)\log n)。

#include<bits/stdc++.h>
#include "keys.h"
#define pb emplace_back
#define fi first
#define se second
#define mp make_pair
using namespace std;
typedef long long ll;
typedef vector<int> vi;
const int maxn=3e5+10;
void cmax(int &x,int y){ x=x>y?x:y; }
void cmin(int &x,int y){ x=x<y?x:y; }
int n,m,num,a[maxn],b[maxn],vis[maxn],vis2[maxn]; queue<int> q;
vector<pair<int,int> > G[maxn];
vi ans,A,vec,cur,col[maxn];
struct DSU{
    int fa[maxn];
    void init(){ for(int i=1;i<=n;i++) fa[i]=i; }
    int find(int u){ return fa[u]==u?u:fa[u]=find(fa[u]); }
    void merge(int u,int v){ fa[u]=find(v); vis[find(v)]=1; }
}dsu;
void init(){
    while(q.size()) q.pop();
    for(auto z:vec) col[z].clear(),b[z]=0;
    cur.clear(); vec.clear();
}
void modify(){
    if(cur.size()<num) ans=cur,num=cur.size();
    else if(cur.size()==num) for(auto u:cur) ans.pb(u);
}
void bfs(int s){
    q.push(s); 
    while(q.size()){
        int u=q.front(); q.pop();
        if(dsu.find(u)!=s){ dsu.merge(s,u); return ; }
        if(vis[u]) continue; 
        vis[u]=1; cur.pb(u);
        if(!b[a[u]]){
            b[a[u]]=1; vec.pb(a[u]);
            for(auto v:col[a[u]]) q.push(v);
        }
        for(auto z:G[u]){
            int v=z.fi,w=z.se;
            if(b[w]) q.push(v);
            else col[w].pb(v),vec.pb(w);
        }
    }
    vis2[s]=1; modify();
}
vi find_reachable(vi R,vi U,vi V,vi C){
    n=R.size(); m=U.size(); dsu.init(); num=n+1;
    for(int i=1;i<=n;i++) a[i]=R[i-1]+1;
    for(int i=1;i<=m;i++){
        int u=U[i-1]+1,v=V[i-1]+1,w=C[i-1]+1;
        G[u].pb(v,w); G[v].pb(u,w);
    }
    while(1){
        bool flag=0; memset(vis,0,sizeof(vis));
        for(int i=1;i<=n;i++){
            if(dsu.find(i)!=i||vis[i]||vis2[i]) continue;
            init(); bfs(i); flag=1;
        }
        if(!flag) break;
    }
    A.clear(); A.resize(n,0); 
    for(auto u:ans) A[u-1]=1;
    return A;
}