CF-1385E Directing Edges
题意
给定一个由有向边与无向边组成的图，现在需要你把所有的无向边变成有向边，使得形成的图中没有环。
如果可以做到请输出该图，否则直接输出"NO"。
分析
我们先只连接有向边，然后做一遍拓扑排序，如果失败了，就说明有环，输出 “NO”。
然后处理剩下的无向边。对于无向边 $(u, v)$，如果 $u$ 的拓扑序小于 $v$，那么令这条边的方向是 $u\rightarrow v$。否则，方向就是 $v\rightarrow u$。因为这条边是从拓扑序小的点指向拓扑序大的点，所以必然不会形成环。
RECORD
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
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
| #include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <vector>
using namespace std;
const int MAXN = 200005;
int n, m;
vector<int> G[MAXN];
int c[MAXN], topo[MAXN], id[MAXN], t, bn, x[MAXN], y[MAXN];
bool dfs(int u) {
c[u] = -1;
for (auto v : G[u]) {
if (c[v] < 0)
return false;
else if (c[v] == 0 && !dfs(v))
return false;
}
c[u] = 1;
topo[--t] = u;
id[u] = t;
return true;
}
bool toposort() {
t = n;
memset(c, 0, sizeof(c));
memset(id, 0, sizeof(id));
memset(topo, 0, sizeof(topo));
for (int i = 1; i <= n; i++)
if (!c[i])
if (!dfs(i)) return false;
return true;
}
int main() {
ios::sync_with_stdio(false);
int t;
cin >> t;
while (t--) {
cin >> n >> m;
for (int i = 1; i <= n; i++) G[i].clear();
bn = 0;
for (int i = 0; i < m; i++) {
int ti, tx, ty;
cin >> ti >> tx >> ty;
if (ti == 0) { // 无向
x[++bn] = tx;
y[bn] = ty;
} else {
G[tx].push_back(ty);
}
}
if (!toposort()) {
cout << "NO\n";
continue;
}
cout << "YES\n";
for (int i = 1; i <= bn; i++) {
if (id[x[i]] <= id[y[i]])
cout << x[i] << " " << y[i] << endl;
else
cout << y[i] << " " << x[i] << endl;
}
for (int i = 1; i <= n; i++) {
for (auto j : G[i]) { cout << i << " " << j << endl; }
}
}
return 0;
}
|
