1 条题解
-
0
欢迎访问我的博客:blog.chungzh.cn
前置知识:拓扑排序
题意
给定一个由有向边与无向边组成的图,现在需要你把所有的无向边变成有向边,使得形成的图中没有环。
如果可以做到请输出该图,否则直接输出"NO"。
分析
我们先只连接有向边,然后做一遍拓扑排序,如果失败了,就说明有环,输出 “NO”。
然后处理剩下的无向边。对于无向边 ,如果 的拓扑序小于 ,那么令这条边的方向是 。否则,方向就是 。因为这条边是从拓扑序小的点指向拓扑序大的点,所以必然不会形成环。
这里用 DFS 的算法实现拓扑排序。
#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; }
- 1
信息
- ID
- 833
- 时间
- 3000ms
- 内存
- 256MiB
- 难度
- 7
- 标签
- 递交数
- 2
- 已通过
- 1
- 上传者