给定一个有向图无环，问最多可以删去多少条边使得图的连通性不变。
首先考虑在什么情况下会被删：假设边((u,v))，那么当且仅当存在一个(w)，使得 (u) 可以到达 (w) ，且 (w) 可以到达 (v) 。
也就是说我们考虑“绕路”。
但是，我们怎么知道这个 (w) 的存在呢？——我们可以维护每一个点到其他点的连通性。
但是我们如果遍历的先后顺序有影响呢？不就统计不到了吗？
所以我们有下面这样的性质：统计一个点延伸出去的最长路，然后先访问最长路长的点。
为什么呢？——因为长的点有可能到达短的点，而短的点不可能到达长的点。
正确性显然。
然后有向图连通性明显使用 bitset 来优化，时间复杂度 (O(frac{nm}{w}))
代码：
#include<bits/stdc++.h>
using namespace std;
template <typename T>
inline void read(T &x){
x=0;char ch=getchar();bool f=false;
while(!isdigit(ch)) f|=ch=='-',ch=getchar();
while(isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
x=f?-x:x;
}
template <typename T>
inline void write(T x){
if(x<0) putchar('-'),x=-x;
if(x>9) write(x/10);
putchar(x%10^48);
}
#define ll long long
const int N=3e4+5,M=1e5+5;
int head[N],nex[M],to[M],idx,vec[N],dist[N];
int n,m,ans;
bool vis[N];
bitset<N> s[N];
void add(int u,int v){
nex[++idx]=head[u];
to[idx]=v;
head[u]=idx;
return ;
}
bool cmp(int x,int y){return dist[x]>dist[y];}
void dfs(int x){
if(vis[x]) return ;
vis[x]=true;int top=0;
for(int i=head[x];i;i=nex[i]){int y=to[i];dfs(y);dist[x]=max(dist[x],dist[y]+1);}
for(int i=head[x];i;i=nex[i]){int y=to[i];vec[++top]=y;}
sort(vec+1,vec+top+1,cmp);
for(int i=1;i<=top;i++){
if(s[x][vec[i]]) ans++;
else s[x]|=s[vec[i]];
}
return ;
}
signed main(){
read(n),read(m);
for(int i=1;i<=m;i++){
int u,v;
read(u),read(v);
add(u,v);
}
for(int i=1;i<=n;i++) s[i][i]=1;
for(int i=1;i<=n;i++) if(!vis[i]) dfs(i);
write(ans);
return 0;
}