题意:给定一个(N)个点(M)条边的有向无环图,如果想要使得原图任意两点的连通性保持不变，最多能删掉多少条边?(N<=30000,M<=100000.)
分析:对于一条边((u,v)),它能被删掉,当且仅当有另外一条路径(u->v)的路径.
对于有向无环图,需要想到拓扑排序,算是一个看到有向无环图的思路之一.
拓扑排序时给每个节点(i)记录一个访问时间(num[i]=tim),然后把每个节点的出边按照到达的节点的访问时间从小到大排序.然后按照访问时间从大到小遍历整张图.开一个(N*N)的(bitset)记录对于每个节点(i),它当前是否能够到达节点(j),如果能则(f[i][j]=1).遍历到一个节点(u)时,扫描和它相连的节点(v),如果(f[u][num[v]])已经等于1了,则这条边是可以删的,否则令(f[u][num[v]]=1),同时(f[u]|=f[v]),表示保留((u,v))这条边之后,v能够到达的点,u通过v都能够到达(根据拓扑序,v在u之前已经更新完了).
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
#include<map>
#include<set>
#include<bitset>
#define ll long long
using namespace std;
inline int read(){
int x=0,o=1;char ch=getchar();
while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar();
if(ch=='-')o=-1,ch=getchar();
while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
return x*o;
}
const int N=30005;
const int M=100005;
int n,m,tim,ans,deg[N],num[N],st[N];
vector<int>g[N];queue<int>q;bitset<N>f[N];
inline void topsort(){
for(int i=1;i<=n;++i)if(!deg[i])q.push(i);
while(q.size()){
int u=q.front();q.pop();
num[u]=++tim;st[tim]=u;
for(int i=0;i<(int)g[u].size();++i){
int v=g[u][i];--deg[v];
if(!deg[v])q.push(v);
}
}
}
inline bool cmp(const int &x,const int &y){return num[x]<num[y];}
int main(){
n=read();m=read();
for(int i=1;i<=m;++i){
int u=read(),v=read();
g[u].push_back(v);++deg[v];
}
topsort();
for(int i=1;i<=n;++i)
if(g[i].size())sort(g[i].begin(),g[i].end(),cmp);
for(int i=tim;i>=1;--i){
int u=st[i];
for(int j=0;j<(int)g[u].size();++j){
int v=g[u][j];
if(f[u][num[v]]==1)++ans;
else f[u][num[v]]=1,f[u]|=f[v];
}
}
printf("%d
",ans);
return 0;
}