CF1385E Directing Edges
Zirnc
2022-08-26 18:08:07
欢迎访问我的博客：[blog.chungzh.cn](https://blog.chungzh.cn/)
[CF-1385E Directing Edges](https://codeforces.com/problemset/problem/1385/E)
前置知识：[拓扑排序](https://blog.chungzh.cn/articles/topo-sort/)
## 题意
给定一个由有向边与无向边组成的图，现在需要你把所有的无向边变成有向边，使得形成的图中**没有环**。
如果可以做到请输出该图，否则直接输出"NO"。
## 分析
我们先只连接有向边，然后做一遍拓扑排序，如果失败了，就说明有环，输出 “NO”。
然后处理剩下的无向边。对于无向边 $(u, v)$，如果 $u$ 的拓扑序小于 $v$，那么令这条边的方向是 $u\rightarrow v$。否则，方向就是 $v\rightarrow u$。因为这条边是从拓扑序小的点指向拓扑序大的点，所以必然不会形成环。
这里用 DFS 的算法实现拓扑排序。
[RECORD](https://codeforces.com/contest/1385/submission/169677796)
```cpp
#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;
}
```