U606887 ATRI - My Dear Moments

hoko · 2025-09-04 20:57:31 · 个人记录

前置算法

并查集

题目分析

首先想到删边不好维护。就应该想到把操作离线下来，按 k 从大到小排序，这样删边就转换成了加边，很好维护。每次只需要把边权大于等于 k 的边加入图中，再用并查集维护一下联通快即可。

考虑处理连边操作，每次连边都会让 a 和 b 两个点的度数都加一，我们先判断它们连边前的度数是否为二，如果是的话，就要让它们各自的联通块的度数为二的点的总数都要减一，加边后判断同理。

然后考虑如何统计答案。对于每个联通块，我们需要知道里面有多少个点以及度数为二的点有多少个，如果它们数量相等，那么就说明这个联通块是一个环，那么对应的答案就要加一。

维护联通块和点数和度数为二的点数都可以用并查集来处理。代码没有什么细节，注意是离线操作，最后要按原顺序输出答案。

代码

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1010101;
ll n,m,fa[N],deg[N],deg2[N],cir[N],q,d,ans[N],siz[N];
struct edge{ll u,v,w;}s[N],p[N];
bool cmp(edge a,edge b){return a.w>b.w;}
ll find(ll x){
    if(fa[x]==x)return x;
    return fa[x]=find(fa[x]);
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++)fa[i]=i,siz[i]=1;
    for(int i=1;i<=m;i++)cin>>s[i].u>>s[i].v>>s[i].w;
    sort(s+1,s+m+1,cmp);
    cin>>q;
    for(int i=1;i<=q;i++)cin>>d,p[i]={i,0,d};
    sort(p+1,p+q+1,cmp);
    ll c=0;
    for(int i=1,j=0;i<=q;i++){
        while(j<m&&s[j+1].w>=p[i].w){
            j++;
            ll x=find(s[j].u),y=find(s[j].v);
            if(deg[s[j].u]==2)deg2[x]--;
            if(deg[s[j].v]==2)deg2[y]--;
            deg[s[j].u]++,deg[s[j].v]++;
            c-=cir[x],cir[x]=0;
            if(x!=y)fa[y]=x,siz[x]+=siz[y],deg2[x]+=deg2[y],c-=cir[y];
            if(deg[s[j].u]==2)deg2[x]++;
            if(deg[s[j].v]==2)deg2[x]++;
            if(deg2[x]==siz[x])c++,cir[x]=1;
        }
        ans[p[i].u]=c;
    }
    for(int i=1;i<=q;i++)cout<<ans[i]<<' ';
    return 0;
}