题解：AT_abc401_e [ABC401E] Reachable Set

laiyouming · 2025-04-27 08:43:35 · 题解

思路

我们发现想要从顶点 1 出发，通过边能够到达的顶点集合恰好为 \{1,2,\ldots,k\} 必须满足集合中的点是连通的，所以用并查集维护，并记录每一个并查集里有多少个数，如果节点 1 所在的并查集里的数少于 i 个，就输出 -1，否则就看 1 所在的并查集里数连向多少个不在集合里的点。

代码

#include <bits/stdc++.h>
using namespace std;
int n,m,b[200010],d[200010],e[200010];
vector<int>a[200001];
set<int>c;
int cz(int x){
    if(b[x]==x){
        return x;
    }
    return b[x]=cz(b[x]);
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++){
        int x,y;
        scanf("%d%d",&x,&y);
        a[x].push_back(y);
        a[y].push_back(x);
    }
    for(int i=1;i<=n;i++){
        b[i]=i,d[i]=1;
    }
    for(auto i:a[1]){
        e[i]=1;
        c.insert(i);
    }
    printf("%d\n",c.size());
    for(int i=2;i<=n;i++){
        for(auto j:a[i]){
            if(j<=i){
                int x=cz(i),y=cz(j);
                if(x!=y){
                    b[x]=y;
                    d[y]+=d[x];
                }
            }
            else{
                if(e[j]==0){
                    e[j]=1;
                    c.insert(j);
                }
            }
        }
        c.erase(i);
        if(d[cz(i)]==i){
            printf("%d\n",c.size());
        }
        else{
            printf("-1\n");
        }
    }
}