题解：AT_abc401_e [ABC401E] Reachable Set

son_son · 2025-04-12 22:30:48 · 题解

思路

看到好多大佬都用了并查集来做，小蒟蒻膜拜，只能给出一个奇奇怪怪的做法。

考虑递增枚举 k 正向加点，可以发现如果这张图满足要求，第 k 个点的来源必定小于 k。所以可以在每次加点的时候把与它相连接的点记下来。

如果第 k 个点没有被记下来，则说明无法完成，输出 -1。

否则，还需要查看是否一到 k 全能被到达。可以发现之前没被收录的那些点只能通过点 k 进行拓展。所以，从 k 跑 dfs。注意，大于 k 的点不跑。最后查看是否所有点都被收录了。

答案就是被收录点集的大小减去 k。

AC Code:

#include<bits/stdc++.h>
using namespace std;
long long n,m,mp[200005],ans;
vector<long long>poi[200005];
inline void dfs(long long now,long long lm){
    for(int i=0;i<poi[now].size();i++){
        if(mp[poi[now][i]]==0){
            ans++;
            mp[poi[now][i]]=1;
            if(poi[now][i]<=lm)dfs(poi[now][i],lm);
        }
    }
}
int main(){
    scanf("%lld%lld",&n,&m);
    for(int i=1;i<=m;i++){
        long long a,b;
        scanf("%lld%lld",&a,&b);
        poi[a].push_back(b);
        poi[b].push_back(a);
    }
    mp[1]=1;
    ans=1;
    for(int i=0;i<poi[1].size();i++){
        mp[poi[1][i]]=1;
        ans++;
    }
    printf("%lld\n",ans-1);
    long long last=1;//优化，只用从上一个成功的 k 往下 check 即可。
    for(int i=2;i<=n;i++){
        if(mp[i]==1){
            dfs(i,i);
            long long flag=1;
            for(int j=last;j<=i;j++){//优化
                if(mp[j]==0){
                    flag=0;
                    break;
                }
            }
            if(flag==1)printf("%lld\n",ans-i),last=i;
            else printf("-1\n");
        }
        else{
            printf("-1\n");
        }
    }
}