2200

Almost Acyclic Graph

出处：CF915D

题目大意：给定一个 $n$ 个点 $m$ 条边有向图，最多可以移除它的一条边，问是否能把它变成有向无环图？

数据范围： $2 \leq n \leq 500, 1 \leq m \leq \min(n(n-1),100000)$

思路：事实上，看到这个数据范围就知道时间复杂度大概是 $O(nm)$ 了，而DAG的显著性质又是拓扑排序，它的时间复杂度是 $O(m)$ ，因此考虑对每个点作一次check。

然而，check应该如何check？注意到去除一条边是把一个点的入度减一，因此直接模拟即可，原来是猜猜题。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39


void solve() {
    int n, m;
    int x, y;
    cin >> n >> m;
    vvi ma(n);
    vi deg(n);
    rep(i, 0, m - 1) {
        cin >> x >> y;
        ma[x - 1].push_back(y - 1);
        deg[y - 1]++;
    }
    queue<int> q;
    auto check = [&](int x) -> bool {
        auto deg2 = deg;
        deg2[x] = max(deg2[x] - 1, 0);
        vi res;
        while (!q.empty()) q.pop();
        rep(i, 0, n - 1) {
            if (!deg2[i]) q.push(i);
        }
        while (!q.empty()) {
            auto node = q.front();
            q.pop();
            res.push_back(node);
            for (int& p : ma[node]) {
                if (--deg2[p] == 0) q.push(p);
            }
        }
        return sz(res) == n;
    };
    rep(i, 0, n - 1) {
        if (check(i)) {
            cout << "YES" << endl;
            return;
        }
    }
    cout << "NO" << endl;
    return;
}