欢迎访问我的博客：blog.chungzh.cn

CF-1385E Directing Edges

前置知识：拓扑排序

题意

给定一个由有向边与无向边组成的图，现在需要你把所有的无向边变成有向边，使得形成的图中没有环。

如果可以做到请输出该图，否则直接输出"NO"。

分析

我们先只连接有向边，然后做一遍拓扑排序，如果失败了，就说明有环，输出 “NO”。

然后处理剩下的无向边。对于无向边 $(u, v)$，如果 $u$ 的拓扑序小于 $v$，那么令这条边的方向是 $u\rightarrow v$。否则，方向就是 $v\rightarrow u$。因为这条边是从拓扑序小的点指向拓扑序大的点，所以必然不会形成环。

这里用 DFS 的算法实现拓扑排序。

RECORD

#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;
}