题解 CF915D 【Almost Acyclic Graph】
青烟绕指柔
2020-02-08 19:01:12
------
我们可以想一下，对于拓扑排序，我们删边的实质是什么？
就是让一个点的入度减一，使得这个点由原来不能放到队列当中，而现在可以到队列当中。
所以我们完全没有必要枚举删边，因为删的很多边实质都是使同一个点的入度减一。
所以我们枚举每个点的入度减一，然后拓扑排序判断环即可。
-----
```cpp
#pragma GCC optimize("-Ofast","-funroll-all-loops")
#include<bits/stdc++.h>
//#define int long long
using namespace std;
const int N=510;
int n,m,dag[N],t[N];
vector<int> g[N];
inline int top_sort(){
int cnt=0; queue<int> q;
for(int i=1;i<=n;i++) if(!dag[i]) q.push(i);
while(q.size()){
int u=q.front(); q.pop(); cnt++;
for(auto to:g[u]) if(--dag[to]==0) q.push(to);
}
return cnt==n;
}
signed main(){
cin>>n>>m;
for(int i=1,a,b;i<=m;i++) scanf("%d %d",&a,&b),g[a].push_back(b),dag[b]++;
for(int i=1;i<=n;i++) t[i]=dag[i];
for(int i=1;i<=n;i++) if(dag[i]){
dag[i]--; if(top_sort()) return puts("YES"),0;
for(int i=1;i<=n;i++) dag[i]=t[i];
}
puts("NO");
return 0;
}
```