AT_abc229_e 题解

· · 题解

题目传送门

思路

可以用并查集解决此题。

用并查集求连通块个数，但由于并查集只能加点而不能删点，所以将所有的删点改为加点，并倒着遍历刚好可以满足要求。

过程

设计数器为 c，初始化为 0，答案序列为 A。

倒着遍历从 N 到 1，设循环变量为 u，代表第 u 条边。先将 A_u 答案记为 c，增加连通块 c\gets c+1。然后遍历与 u 连通的点 v，如果 u 与 v 不连通，则会减少一个连通块，即 c\gets c-1。

最后正序输出所有的 A_u 即可。

AC CODE

#include<bits/stdc++.h>
using namespace std;
int read(){int x=0;char f=1,ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();return x*f;}
const int N=2e5+10;
vector<int>vc[N],a;
int n,m,fa[N];
void _init(){
    for(int i=1;i<=n;++i)
        fa[i]=i;
    return;
}
int _find(int x){
    if(x==fa[x])
        return x;
    fa[x]=_find(fa[x]);
    return fa[x];
}
void _merge(int x,int y){
    int xx=_find(x),yy=_find(y);
    if(xx!=yy)
        fa[xx]=yy;
    return;
}
int main(){
    n=read(),m=read();
    _init();
    while(m--){
        int u=read(),v=read();
        vc[u].push_back(v);
        vc[v].push_back(u);
    }
    int ans=0;
    for(int i=n;i>=1;--i){
        a.push_back(ans++);
        for(auto j:vc[i])
            if(i<j){
                if(_find(i)!=_find(j))
                    --ans;
                _merge(i,j);
            }
    }
    reverse(a.begin(),a.end());
    for(auto i:a)
        printf("%d\n",i);
    return 0;
}