题目链接：http://codeforces.com/contest/915/problem/D
题目大意：
给出一个(n)个结点(m)条边的有向图(无自环、无重边，2 ≤ n ≤ 500, 1 ≤ m ≤ min(n(n - 1), 100000) )，问能否通过删除其中的某一条边，使得该图无环。
知识点： 拓扑排序、DFS
解题思路一：
由于结点数不多，所以可以枚举每个入度不为(0)的点，删去通向它的一条边（即使其入度减一），再跑拓扑排序判断有没有环。
AC代码一：
1 #include <bits/stdc++.h>
2
3 using namespace std;
4 const int maxn = 520, maxm = 100003;
5 vector<int> G[maxn];
6 int in[maxn],tin[maxn],stac[maxn];
7
8 bool topo(int n){
9 int top=0,ending=0;
10 for(int i=1;i<=n;i++){
11 if(tin[i]==0)
12 stac[ending++]=i;
13 }
14 while(top<ending){
15 int now=stac[top];
16 for(int i=0;i<G[now].size();i++){
17 tin[G[now][i]]--;
18 if(tin[G[now][i]]==0) stac[ending++]=G[now][i];
19 }
20 top++;
21 }
22 return ending>=n;
23 }
24 int main(){
25 int n,m;
26 scanf("%d%d",&n,&m);
27 for(int i=0;i<m;i++){
28 int u,v;
29 scanf("%d%d",&u,&v);
30 in[v]++;
31 G[u].push_back(v);
32 }
33 for(int i=1;i<=n;i++){
34 if(in[i]!=0){
35 for(int j=1;j<=n;j++) tin[j]=in[j];
36 tin[i]--;
37 if(topo(n)) return 0*puts("YES");
38 }
39 }
40 return 0*puts("NO");
41 }
解题思路二：
先找出一个简单环，然后枚举删除该环上的每一条边，再跑拓扑排序判断还有没有环。
AC代码二：
#include <bits/stdc++.h>
using namespace std;
const int maxn = 520;
vector<int> G[maxn];
int mark[maxn],in[maxn],tin[maxn],last[maxn];
int cnt, loop[maxn];//cnt记录环上的结点数
bool dfs(int rt,int la){
last[rt]=la;
mark[rt]=1; //访问过的结点,mark=1;
for(int i=0;i<G[rt].size();i++){
if(mark[G[rt][i]]==0){ //没有访问过的结点, mark=0
if(dfs(G[rt][i],rt)) return true;
}
if(mark[G[rt][i]]==1){
int now=rt;
cnt=0;
while(now!=G[rt][i]&&now!=-1){
loop[cnt++]=now;
now=last[now];
}
loop[cnt++]=G[rt][i];
return true;
}
}
mark[rt]=-1; //访问过并且会走到死路的结点，mark=-1
return false;
}
int stac[maxn];
bool topo(int n,int from,int to){//拓扑排序检查是否有环
int top=0,ending=0;
for(int i=1;i<=n;i++){
if(tin[i]==0)
stac[ending++]=i;
}
while(top<ending){
int now=stac[top];
for(int i=0;i<G[now].size();i++){
if(now==from&&G[now][i]==to) continue;
tin[G[now][i]]--;
if(tin[G[now][i]]==0) stac[ending++]=G[now][i];
}
top++;
}
return ending>=n;
}
int main(){
int n,m;
scanf("%d%d",&n,&m);
for(int i=0;i<m;i++){
int u,v;
scanf("%d%d",&u,&v);
G[u].push_back(v);
in[v]++; //记录入度
}
for(int i=1;i<=n;i++){
if(mark[i]==0){
if(dfs(i,-1)) break;
}
}
if(!cnt) return 0*puts("YES");
for(int i=0;i<cnt;i++){
for(int j=1;j<=n;j++) tin[j]=in[j];
tin[loop[(i+1)%cnt]]--;
if(topo(n,loop[i],loop[(i+1)%cnt])) return 0*puts("YES");
}
return 0*puts("NO");
}