题解：AT_abc401_e [ABC401_e] Reachable Set

· · 题解

原题传送门

首先如果说对于某个 k 存在解，意味着从一出发，只经过编号小于等于 k 的点，能够到达所有编号小于等于 k 的点。

考虑从小到大利用并查集维护连通性。从小到大枚举每个点，把这个点所有连向编号小于等于 k 点的边的两端并在一起。这样每次结束后所有小于等于 k 点都和 1 并在一起说明可以走到。

直接暴力检查是 O(n^2) 的。假设在处理完一个点后我们用某种奇妙的方法知道了哪些点和一并在一起，哪些点没有。我们把没有并在一起的点全部扔进一个队列。每处理到一个新点也把他扔进队列。

遍历队列元素，如果当前元素和 1 并起来了就出队列，否则直接 break。

显然一个点只要跟 1 并上了，在今后整个过程中也能并上。所以用上述过程遍历队列后，如果队列为空说明有解。

只要确定有解就很简单了。所有与小于等于 k 的点=一条边直接相连的点必须删（否则通过这条边肯定能到）。所有不与小于等于 k 的点直接相连的都不用删（因为删完了直接相邻的边，没有可能到这些点）。

维护多少个点直接相连较为简单，可以见代码部分。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 3000100;
int n,m,tot;
struct edge{
    int nxt,to;
}e[N*2];
bool vis[N]; //记录这个点有没有计入答案的计算
int ans;
int head[N],cnt;
inline void add(int u,int v){
    e[++cnt].nxt=head[u];
    e[cnt].to=v;
    head[u]=cnt;
}
int f[N];
queue <int> q;
int find(int x){
    if(f[x]==x) return x;
    else return f[x]=find(f[x]);
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++) f[i]=i;
    for(int i=1;i<=m;i++){
        int u,v;
        cin>>u>>v;
        add(u,v); add(v,u);
    }
    for(int i=1;i<=n;i++){
        if(vis[i]) ans--; //清除这个点对答案的影响
        q.push(i);
        for(int j=head[i];j;j=e[j].nxt){
            int v=e[j].to;
            if(v<=i){
                int U=find(i),V=find(v);
                if(U!=V) f[U]=V;
            }else if(!vis[v]){
                vis[v]=true;
                ans++;
            }
        }
        while(!q.empty()){
            int u=q.front();
            if(find(u)!=find(1)) break;
            q.pop();
        }
        if(!q.empty()) cout<<-1<<'\n';
        else cout<<ans<<'\n';
    }
    return 0;
}