DDOSvoid's Blog

CF 915D Almost Acyclic Graph

发表于 更新于 分类于
本文字数： 1.3k 阅读时长 ≈ 1 分钟

题目描述

http://codeforces.com/problemset/problem/915/D

简要题意：给定一个 $n$ 个点 $m$ 条边的有向图，问是否可以删除至多一条边，使得原图变成有向无环图

$n\le 500,m\le 10^5$

Solution

第一想法肯定是枚举删那条边，然后拓扑排序，然而这样复杂度就炸了

注意到拓扑排序中一条边只有它的终点有用，所以我们只需要枚举那个点的入度减 $1$ 即可

时间复杂度 $O(nm)$

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
40
41
42
43
44
45
46
47
48
49
50
51
52
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#define maxn 510
#define maxm 100010
using namespace std;

int n, m;

struct Edge {
    int to, next;
} e[maxm]; int c1, head[maxn], in[maxn], In[maxn];
inline void add_edge(int u, int v) {
    e[c1].to = v; e[c1].next = head[u]; head[u] = c1++;
}

int id[maxn];
bool topsort() {
    queue<int> Q;
    for (int i = 1; i <= n; ++i)
        if (!in[i]) Q.push(i);
    int cnt = 0; 
    while (!Q.empty()) {
        int u = Q.front(); Q.pop(); ++cnt;
        for (int i = head[u]; ~i; i = e[i].next) {
            int v = e[i].to;
            if (--in[v] == 0) Q.push(v); 
        }
    }
    return cnt == n; 
} 

int main() { fill(head, head + maxn, -1); 
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    cin >> n >> m;
    for (int i = 1; i <= m; ++i) {
        int x, y; cin >> x >> y;
        add_edge(x, y); ++in[y];
    }
    for (int i = 1; i <= n; ++i) In[i] = in[i];
    for (int i = 1; i <= n; ++i) {
        if (!In[i]) continue;
        for (int j = 1; j <= n; ++j) in[j] = In[j];
        --in[i]; if (topsort()) return cout << "YES" << "\n", 0; 
    }
    cout << "NO" << "\n"; 
    return 0;
}