[BZOJ4484] [JSOI2015] 最小表示[拓扑排序+bitset]

题意

给你一个 \(n\) 个点 \(m\) 条边的 \(\rm DAG\) ，询问最多能够删除多少条边，使得图的连通性不变

• \(n\leq 3\times 10^4\ ,m\leq 10^5\) 。

分析

• 假设有点 \(u,v,x\) ，且有边 \(u \rightarrow v,\ u \rightarrow x,\ x \rightarrow v\)，那么此时 \(u \rightarrow v\) 这条边可以被删除。

• 于是直接拓扑排序，利用 \(bitset\) 求出每个点可以到达的点集合可以被到达的点集。

• 对于每个点再搞一个 \(bitset\) 表示这个点连了边的集合。

• 如果一个点 \(v\) 可以被删除，那么显然\(u\) 可以从它连向的其他点走到 \(v\)。
  因为无环所以不存在双向依赖的关系，也就是说一条边能不能删并不被其他边是否能删所影响。

• 总时间复杂度为 \(O(m*\frac{n}{32})\)。

代码

#include<bits/stdc++.h>
using namespace std;
#define go(u) for(int i=head[u],v=e[i].to;i;i=e[i].last,v=e[i].to)
#define rep(i,a,b) for(int i=a;i<=b;++i)
#define pb push_back
#define re(x) memset(x,0,sizeof x)
typedef long long LL;
inline int gi(){
    int x=0,f=1;char ch=getchar();
    while(!isdigit(ch)) {if(ch=='-') f=-1;ch=getchar();}
    while(isdigit(ch)){x=(x<<3)+(x<<1)+ch-48;ch=getchar();}
    return x*f;
}
template<typename T>inline bool Max(T &a,T b){return a<b?a=b,1:0;}
template<typename T>inline bool Min(T &a,T b){return b<a?a=b,1:0;}
const int N=1e5 + 7;
int n,m,edc=1,ans;
int head[N],ind[N];
bitset<30004>to[30004],bto[30004],tmp;
struct edge{
    int last,to;
    edge(){}edge(int last,int to):last(last),to(to){}
}e[N*2];
void Add(int a,int b){
    e[++edc]=edge(head[a],b),head[a]=edc;
    e[++edc]=edge(head[b],a),head[b]=edc;
}
int q[N],hd=1,tl;
void topo(){
    rep(i,1,n) if(!ind[i]) q[++tl]=i;
    for(;hd<=tl;++hd){
        int u=q[hd];
        go(u)if(!(i&1))
            if(--ind[v]==0) q[++tl]=v;
    }
    for(int j=tl;j;--j){
        int u=q[j];to[u][u]=1;
        go(u)if(i&1) to[v]|=to[u];
    }
    for(int j=1;j<=tl;++j){
        int u=q[j];bto[u][u]=1;
        go(u)if(!(i&1)) bto[v]|=bto[u];
    }
}
int main(){
    n=gi(),m=gi();
    rep(i,1,m){
        int a=gi(),b=gi();
        Add(a,b);++ind[b];
    }
    topo();
    for(int u=1;u<=n;++u){
        tmp.reset();
        go(u)if(!(i&1)) tmp[v]=1;
        go(u)if(!(i&1)&&(tmp&bto[v]).count()>1) ++ans;
    }
    printf("%d\n",ans);
    return 0;
}

[BZOJ4484] [JSOI2015] 最小表示[拓扑排序+bitset]

原文：https://www.cnblogs.com/yqgAKIOI/p/9797785.html