3696. 构造有向无环图

Powered by:NEFU AB-IN

Link

3696. 构造有向无环图

• 题意

  Codeforces Round 656 (Div. 3) E

  给定一个由 n个点和 m条边构成的图。
  不保证给定的图是连通的。
  图中的一部分边的方向已经确定，你不能改变它们的方向。
  剩下的边还未确定方向，你需要为每一条还未确定方向的边指定方向。
  你需要保证在确定所有边的方向后，生成的图是一个有向无环图（即所有边都是有向的且没有有向环的图）。

• 思路

  自己想的思路，可能偏麻烦

  • 首先，将带方向的边连起来形成一个图g1，不带方向的边连起来，形成另一个图g
  • 其次，对g1进行拓扑排序 $O(n+m)$
    • 在拓扑排序途中，当遍历到一个节点u时
      • 首先判断，它是不是已经遍历过了，或者在g1图中，还有边指向它。如果存在其中一种情况，说明不能作为遍历的点，可以直接pop
    • 其次，可以得出结论，那么根据这个点u，在g图中遍历u的邻点v。首先，判断是否v已经在u前出队了，也就是拓扑序在前面，若没有的话，就在g图中连上 u到v的有向边，并且别忘了更新度
    • 后面就跟拓扑排序一样了
  • 最后，我们所有的边都在g1图中，那么dfs每个点，并标记，即可得出所有边
  • 另外，当g1图本身成环，或者，最后输出的拓扑序列不是n个，那么都是无解

• 代码

  /*
  * @Author: NEFU AB-IN
  * @Date: 2023-03-01 23:23:00
  * @FilePath: \Acwing\3696\3696.cpp
  * @LastEditTime: 2023-03-01 23:58:06
  */
  #pragma GCC optimize(1)
  #pragma GCC optimize(2) // 先开优化
  #pragma GCC optimize(3, "Ofast", "inline")
  #include <bits/stdc++.h>
  using namespace std;
  #define int long long
  #undef int#define SZ(X) ((int)(X).size())
  #define ALL(X) (X).begin(), (X).end()
  #define IOS                                                                                                            \ios::sync_with_stdio(false);                                                                                       \cin.tie(nullptr);                                                                                                  \cout.tie(nullptr)
  #define DEBUG(X) cout << #X << ": " << X << '\n'
  typedef pair<int, int> PII;const int N = 3e5 + 10, INF = 0x3f3f3f3f;int deg[N];
  bool st[N], vis[N];
  void solve()
  {int n, m;cin >> n >> m;memset(st, 0, (n + 1));memset(deg, 0, (n + 1) * 4);memset(vis, 0, (n + 1));vector<int> g[n + 1], g1[n + 1];for (int i = 1; i <= m; ++i){int t, a, b;cin >> t >> a >> b;if (t){g1[a].push_back(b);deg[b]++;}else{g[a].push_back(b);g[b].push_back(a);}}queue<int> q;for (int i = 1; i <= n; ++i){if (!deg[i])q.push(i);}if (!SZ(q)){cout << "NO\n";return;}int cnt = 0;while (SZ(q)){auto u = q.front();q.pop();if (st[u] || deg[u])continue;for (auto &v : g[u]){if (!st[v]){g1[u].push_back(v);deg[v]++;}}st[u] = true; // 表示已经释放出去了cnt++;for (auto &v : g1[u]){if (!--deg[v]){q.push(v);}}}if (cnt != n){cout << "NO\n";return;}cout << "YES\n";function<void(int)> dfs = [&](int u) {vis[u] = 1;for (auto &v : g1[u]){cout << u << " " << v << '\n';if (!vis[v])dfs(v);}};for (int i = 1; i <= n; ++i){if (!vis[i])dfs(i);}return;
  }signed main()
  {IOS;int T;cin >> T;while (T--)solve();return 0;
  }