大意：给出一个有向图，问能否在只去掉一条边的情况下破掉所有的环
解析：最直接的是枚举每个边，将其禁用，然后在图中找环，如果可以就YES，都不行就NO
复杂度O(N*M)看起来不超时
但是实现了以后发现即使优化到不清空vis数组（时间戳标记），也仍然超时。
因为O(N*M)已经很接近时间复杂度上界，常数稍大就GG。
不过可以脑补一下取巧算法：在不超时的前提下，随机取K个边进行检验~~~。不过数据多了就非常容易GG。理论上还是可行的。
正解：从枚举边变为枚举点，删掉到达一个点的某条边可以认为是该点入度 -1 ，然后做拓扑排序。
如果所有点都能访问到，说明没有环，YES。
如果有的点不能访问到，则说明图中存在环，删到达该点的某条边不可行。
入度 -1 的正确性：
可以认为是暂时不具体考虑删掉的是那条边，到了这个点的入边只剩一个没有访问的时候，该点的入度为0，可以开始以该点为起点dfs（bfs也行），如果该点正好在某个环内，就直接破掉（遍历）了这个环。、
1 /* 2 Welcome Hacking 3 Wish You High Rating 4 */ 5 #include6 #include 7 #include 8 #include 9 #include 10 #include 11 #include 12 #include 13 using namespace std;14 int read(){15 int xx=0,ff=1;char ch=getchar();16 while(ch>'9'||ch<'0'){ if(ch=='-')ff=-1;ch=getchar();}17 while(ch>='0'&&ch<='9'){xx=(xx<<3)+(xx<<1)+ch-'0';ch=getchar();}18 return xx*ff;19 }20 const int maxn=510,maxm=100010;21 int N,M,lin[maxn],len,in_[maxn],deg[maxn];22 struct edge{23 int y,next;24 }e[maxm];25 inline void insert(int xx,int yy){26 e[++len].next=lin[xx];27 lin[xx]=len;28 e[len].y=yy;29 in_[yy]++;30 }31 bool vis[maxn];32 void dfs(int x){33 vis[x]=1;34 for(int i=lin[x];i;i=e[i].next){35 deg[e[i].y]--;36 if(!vis[e[i].y]){37 if(deg[e[i].y]<=0)38 dfs(e[i].y);39 }40 }41 }42 int main(){43 //freopen("in.txt","r",stdin);44 N=read(),M=read();45 for(int i=1;i<=M;i++){46 int t1=read(),t2=read();47 insert(t1,t2);48 }49 for(int i=1;i<=N;i++){50 for(int j=1;j<=N;j++)51 deg[j]=in_[j];52 memset(vis,0,sizeof(vis));53 deg[i]--;54 for(int j=1;j<=N;j++)55 if((!vis[j])&°[j]<=0)56 dfs(j);57 bool OK=1;58 for(int j=1;j<=N;j++)59 if(!vis[j]){60 OK=0;61 break;62 }63 if(OK){64 printf("YES\n");65 return 0;66 }67 }68 printf("NO\n");69 return 0;70 }