题意
给你一个 (n) 个点 (m) 条边的 ( m DAG) ，询问最多能够删除多少条边，使得图的连通性不变
- (nleq 3 imes 10^4 ,mleq 10^5) 。
分析
-
假设有点 (u,v,x) ，且有边 (u ightarrow v, u ightarrow x, x ightarrow v)，那么此时 (u ightarrow 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
",ans);
return 0;
}