【故事背景】
还记得去年JYY所研究的强连通分量的问题吗？去年的题目里，JYY研究了对于有向图的“加边”问题。对于图论有着强烈兴趣的JYY，今年又琢磨起了“删边”的问题。
【问题描述】
对于一个N个点（每个点从1到N编号），M条边的有向图，JYY发现，如果从图中删去一些边，那么原图的连通性会发生改变；而也有一些边，删去之后图的连通性并不会发生改变。
JYY想知道，如果想要使得原图任意两点的连通性保持不变，我们最多能删掉多少条边呢？
为了简化一下大家的工作量，这次JYY保证他给定的有向图一定是一个有向无环图（JYY：大家经过去年的问题，都知道对于给任意有向图的问题，最后都能转化为有向无环图上的问题，所以今年JYY就干脆简化一下大家的工作?）。
输入一行包含两个正整数N和M。
接下来M行，每行包含两个1到N之间的正整数x_i和y_i，表示图中存在一条从x_i到y_i的有向边。
输入数据保证，任意两点间只会有至多一条边存在。
N<=30,000,M<=100,000
输出一行包含一个整数，表示JYY最多可以删掉的边数。
先求出这个图的拓扑序.
按拓扑序倒着做.中途可以求出一个点到出度为0的点的最大距离.
访问到一个点x的时候.
把它所有指向的点按之前求的距离从大到小排序.
然后枚举每个它指向点.如果这个点在之前已经可以从当前点访问到,那这条边显然多余.
用bitset维护一下每个点和其他点的联通情况即可.
总结： 贪心+动态规划+bitset维护连通性
神奇的是我写记忆话搜索总是re。
1 #include<bits/stdc++.h> 2 using namespace std; 3 int const N=30000+10; 4 int const M=100000+10; 5 struct edge{ 6 int to,nt; 7 }e[M]; 8 int n,m,h[N],cnt,f[N],ind[N],ans,t[N],q[N]; 9 bitset<N> s[N]; 10 int cmp(int x,int y){ 11 return f[x]>f[y]; 12 } 13 void add(int a,int b){ 14 e[++cnt].to=b; 15 e[cnt].nt=h[a]; 16 h[a]=cnt; 17 } 18 void solve(){ 19 int cl=0; 20 for(int i=1;i<=n;i++) 21 if(!ind[i]) q[cl++]=i; 22 for(int i=0;i<cl;i++){ 23 int x=q[i]; 24 for(int j=h[x];j;j=e[j].nt){ 25 int v=e[j].to; 26 if(!--ind[v]) q[cl++]=v; 27 } 28 } 29 for(int i=cl-1;i>=0;i--){ 30 int x=q[i],num=0; 31 f[x]=1; 32 s[x][x]=1; 33 for(int j=h[x];j;j=e[j].nt){ 34 int v=e[j].to; 35 t[++num]=v; 36 f[x]=max(f[x],f[v]+1); 37 } 38 sort(t+1,t+num+1,cmp); 39 for(int j=1;j<=num;j++) 40 if(s[x][t[j]]==0) 41 s[x]|=s[t[j]]; 42 else ans++; 43 } 44 } 45 int main(){ 46 scanf("%d%d",&n,&m); 47 for(int i=1;i<=m;i++){ 48 int x,y; 49 scanf("%d%d",&x,&y); 50 add(x,y); 51 ind[y]++; 52 } 53 solve(); 54 printf("%d\n",ans); 55 return 0; 56 } 57
原文：https://www.cnblogs.com/ZJXXCN/p/11418276.html
