AcWing - 3696. 构造有向无环图

Solost

2023 年 03 月 30 日

241 次浏览

暂无评论

1322字数

题目题解

![image.png](https://amarantos.oss-cn-hangzhou.aliyuncs.com/typecho/2023%2F03%2F30%2Fimage.png)

## 题目链接

[题目链接](https://www.acwing.com/problem/content/3699/)

## 题目大意

这道题就是给你一堆边，有些边是确定方向的，有些边是不确定方向的，问你将这些不确定方向的边怎么放满足这个图是一个有向无环图

## 题解

这道题问是不是有向无环图，那么就是问是不是拓扑图，所以要进行拓扑排序，如果已有的边已经不是拓扑图，那么怎么加边也不是拓扑图，所以先判断给的确定的边是不是拓扑图，如果是拓扑图，那么肯定会算出来一个拓扑序，然后把那些不确定的边按照拓扑序排列即可。这个鬼题别忘了将所有的全局变量都初始化，要不然出现一堆什么鬼，pos标记的时候刚开始用的是vector开了n的大小，我就不知道为啥会报错，换成map就过了。

~~~cpp
#include <algorithm>
#include <bitset>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <fstream>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <unordered_map>
#include <unordered_set>
#include <vector>

using namespace std;
#define x first
#define y second
#define endl '\n'
#define IOS                       \
    ios_base::sync_with_stdio(0); \
    cin.tie(0);                   \
    cout.tie(0);
typedef long long ll;
typedef pair<int, int> PII;
typedef unsigned long long ull;
const int INF = 0x3f3f3f3f, mod = 1000000007;
const int N = 2e5 + 10;
int n, m;
int d[N];
vector<int> ans;
vector<PII> v;
vector<int> a[N];
bool topsort()
{
    queue<int> q;
    for (int i = 1; i <= n; i++) {
        if (!d[i])
            q.push(i);
    }
    while (q.size()) {
        auto t = q.front();
        ans.push_back(t);
        q.pop();
        for (auto x : a[t]) {
            if (--d[x] == 0) {
                q.push(x);
            }
        }
    }
    return ans.size() == n;
}

void solve()
{
    memset(d, 0, sizeof d);
    ans.clear();
    v.clear();
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        a[i].clear();
    }
    while (m--) {
        int op, x, y;
        cin >> op >> x >> y;
        if (op) {
            a[x].push_back(y);
            d[y]++;
        } else {
            v.push_back({ x, y });
        }
    }
    if (!topsort())
        cout << "NO\n";
    else {
        cout << "YES\n";
        unordered_map<int, int> pos;
        for (int i = 0; i < ans.size(); i++) {
            pos[ans[i]] = i;
        }
        for (int i = 1; i <= n; i++) {
            for (auto x : a[i]) {
                cout << i << " " << x << endl;
            }
        }
        for (auto [x, y] : v) {
            if (pos[x] > pos[y])
                cout << y << " " << x << endl;
            else
                cout << x << " " << y << endl;
        }
    }
}
int main()
{
    IOS;
    int t = 1;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}
~~~

最后修改：2023 年 03 月 30 日