Codeforces 915D(拓扑排序)

Codeforces 915D
题意：给出一个有向图，这个图有可能有一条边删去后整幅图变为DAG，求该图是否能变成DAG。
环可以想到拓扑排序，但$m$大，不能枚举边去删。删边的本质在拓扑排序中就是入点的入度减一，所以枚举每一个点入度减一，然后拓扑排序看是否有环，就可以判断了

Codeforces Submission

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
#include<queue>
using namespace std;
#define ms(i, j) memset(i, j, sizeof i)
#define ll long long
vector<int> G[505];
int n, m, ino[505], ino2[505], tot;
bool topsort() {
    queue<int> q;
    for (int i = 1; i <= n; i++) if (ino2[i] == 0) tot++, q.push(i);
    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (int i = 0; i < (int)G[u].size(); i++) {
            int v = G[u][i];
            ino2[v]--;
            if (ino2[v] == 0) tot++, q.push(v);
            if (ino2[v] < 0) ino2[v] = 0;
        }
    }
    if (tot == n) return 1; else return 0;
}
void clean() {
    tot = 0, ms(ino, 0);
}
int solve() {
    clean();
    for (int u, v, i = 1; i <= m; i++) {
        scanf("%d%d", &u, &v);
        G[u].push_back(v), ino[v]++;
    }
    for (int i = 1; i <= n; i++) {
        memcpy(ino2, ino, sizeof ino);
        if (!ino2[i]) continue;
        ino2[i]--, tot = 0;
        if (topsort()) return printf("YES\n"), 0;
    }
    printf("NO\n");
    return 0;
}
int main() {
    scanf("%d%d", &n, &m), solve();
    return 0;
}