[COCI 2023/2024 #1] Mostovi

· · 题解

考虑建一个 DFS 树，那么非树边都是返祖边。

考虑 (u,v) 这样一条非树边，这里 u 是 v 的祖先。在删掉 u 和 v 之后图长这样：

这里紫色部分和红色部分都可能不存在，但由于我们限定这是一条非树边因此绿色部分一定存在。u 上面的部分也可能不存在，但稍后我们会看到这并不影响判断，

首先红色部分必须存在向上的连边否则就会和绿色部分分开。因此我们可以把红色部分和 u 上面的部分看作一个整体。当 u 为根节点的时候红色部分不存在，不过这不会影响我们的判断。

注意到绿色部分也是一个整体的连通块，紫色部分会构成若干连通块。那么紫色部分的每个子树要么和绿色部分有连边，要么和红色部分有连边（且红色部分存在）。我们分几类情况讨论：

考虑三种情况怎么判，发现只需要维护某个子树内最浅和最深的一条返祖边，可以用线段树合并或启发式合并求出。对于第三种情况，绿色部分可以写成 DFS 序上的 O(1) 个连续段，维护 DFS 序区间最小值即可。对于求出绿色部分顶端的点，发现本质上是树上 k 级祖先。

接下来我们考虑树边怎么判。设 u=fa_v，有以下情况：

时间复杂度：O(m\log n) 或 O(m\log^2n)。

//-DYUNQIAN -std=c++14 -O2 -Wall
#include<bits/stdc++.h>

#define ll long long
#define fi first
#define se second
#define mk make_pair

using namespace std;

inline int read(){
    int x=0,f=1;char c=getchar();
    for(;(c<'0'||c>'9');c=getchar()){if(c=='-')f=-1;}
    for(;(c>='0'&&c<='9');c=getchar())x=x*10+(c&15);
    return x*f;
}

void cmax(int &x,int v){x=max(x,v);}
void cmin(int &x,int v){x=min(x,v);}

const int N=3e5+5;
vector<int>G[N],adj[N];
vector<int>R[N];
set<int>S[N];
int n,m;

struct SegTree{
    int M,k,d[N<<2];
    void upd(int p){d[p]=min(d[p<<1],d[p<<1|1]);}
    void build(int n,vector<int>A){
        k=0,M=1;while(M<n)M<<=1,k++;
        for(int i=1;i<=M+M;i++)d[i]=n+1;
        for(int i=1;i<=n;i++)d[i+M-1]=A[i];
        for(int i=M-1;i>=1;i--)upd(i);
    }
    int qmin(int l,int r){
        int res=n+1;
        for(l+=M-1,r+=M;l<r;l>>=1,r>>=1){
            if(l&1)cmin(res,d[l++]);
            if(r&1)cmin(res,d[--r]);
        }
        return res;
    }
}T;

int dep[N],fa[N],sz[N],dfn[N],top[N],hson[N],dfc,pos[N],id[N];
void dfs1(int u,int de){
    dep[u]=de,sz[u]=1;
    for(int v:G[u]){
        if(v==fa[u])continue;
        fa[v]=u,dfs1(v,de+1),sz[u]+=sz[v];
        if(sz[v]>sz[hson[u]])hson[u]=v;
    }
}
void dfs2(int u,int tp){
    top[u]=tp,dfn[u]=++dfc,id[dfc]=u;
    if(hson[u])dfs2(hson[u],tp);
    for(int v:G[u]){
        if(v==fa[u]||v==hson[u])continue;
        dfs2(v,v);
    }
}
int getnode(int u,int v){
    assert(dfn[v]>=dfn[u]&&dfn[v]<=dfn[u]+sz[u]-1);
    int de=dep[u]+1;
    while(dep[top[v]]>de)v=fa[top[v]];
    int dis=dep[v]-de;
    return id[dfn[v]-dis];
}

struct BIT{
    int c[N];
    void clear(){memset(c,0,sizeof(c));}
    int lowbit(int x){return x&(-x);}
    void Add(int x,int v){for(int i=x;i<=n;i+=lowbit(i))c[i]+=v;}
    int sum(int x){int res=0;for(int i=x;i;i-=lowbit(i))res+=c[i];return res;}
    void add(int l,int r,int v){if(l<=r)Add(r+1,-v),Add(l,v);}
    int qval(int x){return sum(x);}
}W;

signed main(void){

#ifdef YUNQIAN
    freopen("in.in","r",stdin);
//    freopen("out.out","w",stdout);
#endif

    n=read(),m=read();
    vector<pair<int,int> >E;vector<int>deg(n+1,0);
    for(int i=1;i<=m;i++){
        int u=read(),v=read();E.emplace_back(mk(u,v));
        adj[u].emplace_back(v),adj[v].emplace_back(u),deg[u]++,deg[v]++;
    }

    vector<bool>vis(n+1,0);
    function<void(int,int)>buildtree=[&](int u,int fa){
        vis[u]=1;
        for(int v:adj[u]){
            if(!vis[v])dep[v]=dep[u]+1,buildtree(v,u),G[u].emplace_back(v);
            else if(dep[v]<dep[u]&&v!=fa)R[u].emplace_back(v);
        }
    };
    dep[1]=1,buildtree(1,0);
    dfs1(1,1),dfs2(1,1);

    vector<int>val(n+1,n+1);
    for(int i=1;i<=n;i++){
        for(int j:R[i])cmin(val[dfn[i]],dep[j]);
    }
    T.build(n,val);

    auto Merge=[&](set<int>&A,set<int>&B){
        if(A.size()<B.size())swap(A,B);
        for(int x:B)A.insert(x);B.clear();
    };

    vector<int>mxlow(n+1,0),mnlow(n+1,0);// max/min low
    function<void(int)>getlow=[&](int u){
        for(int v:G[u])getlow(v),Merge(S[u],S[v]);
        for(int j:R[u])S[u].insert(dep[j]);
        S[u].erase(S[u].lower_bound(dep[u]-1),S[u].end());
        if(S[u].size())mxlow[u]=*--S[u].end(),mnlow[u]=*S[u].begin();
        else mxlow[u]=0,mnlow[u]=n+1;
    };
    getlow(1);

    W.clear();vector<int>cut(n+1,0);

    fill(vis.begin(),vis.end(),0);
    map<pair<int,int>,bool>Ans;

    auto addres=[&](int u,int v){Ans[mk(u,v)]=Ans[mk(v,u)]=1;};
    auto getans=[&](int u){
        // (u,son[u]) | (anc[u],u)
        if(u==1){
            if(G[u].size()>=3)return ;
            if(G[u].size()==2){
                for(int v:G[u])if(sz[v]==1)addres(u,v);
            }
            if(G[u].size()==1){
                int v=G[u][0];
                if(G[v].size()<=1)addres(u,v);
            }
            return ;
        }
        for(int v:G[u]){
            if(mnlow[v]==mxlow[v])vis[mnlow[v]]=1;
            W.add(mnlow[v]+1,mxlow[v]-1,1);
        }
        for(int v:G[u]){
            if(mnlow[v]>=dep[u])cut[u]--;
            if(cut[u]==0){
                bool chk=1;
                for(int j:G[v])if(mnlow[j]>=dep[u])chk=0;
                if(chk)addres(u,v);
            }
            if(mnlow[v]>=dep[u])cut[u]++;
        }

        if(cut[u]>=1)goto ED2;
        for(int j:R[u]){
            int x=getnode(j,u);
            if(mnlow[x]>=dep[j])cut[j]--;
            if(cut[j]==0){
                if(vis[dep[j]])goto ED;
                if(W.qval(dep[j])>=1){addres(u,j);goto ED;}
                if(j==1){addres(u,j);goto ED;}
                if(T.qmin(dfn[x],dfn[u]-1)<dep[j]||T.qmin(dfn[u]+sz[u],dfn[x]+sz[x]-1)<dep[j])addres(u,j);
            }
            ED:if(mnlow[x]>=dep[j])cut[j]++;
        }

        ED2:for(int v:G[u]){
            if(mnlow[v]==mxlow[v])vis[mnlow[v]]=0;
            W.add(mnlow[v]+1,mxlow[v]-1,-1);
        }
    };

    for(int i=1;i<=n;i++)for(int j:G[i])cut[i]+=(mnlow[j]>=dep[i]);
    for(int i=1;i<=n;i++)getans(i);
    int res=0;for(auto e:E)res+=(Ans[mk(e.fi,e.se)]==0);cout<<res<<endl;

    return 0;
}