摘要
Title: 3696. 构造有向无环图
Tag: 拓扑排序
Memory Limit: 64 MB
Time Limit: 1000 ms

3696. 构造有向无环图

题意

Codeforces Round 656 (Div. 3) E

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

自己想的思路，可能偏麻烦
- 首先，将带方向的边连起来形成一个图g1，不带方向的边连起来，形成另一个图g
- 其次，对g1进行拓扑排序 $O(n+m)$ $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;
}

3696. 构造有向无环图

题意

思路

代码