AcWing第4场周赛 — C. 构造有向无环图

题目链接

题面

给定一个由 $n$ 个点和 $m$ 条边构成的图。

不保证给定的图是连通的。

图中的一部分边的方向已经确定，你不能改变它们的方向。

剩下的边还未确定方向，你需要为每一条还未确定方向的边指定方向。

你需要保证在确定所有边的方向后，生成的图是一个有向无环图（即所有边都是有向的且没有有向环的图）。

输入格式

第一行包含整数 $T$，表示共有 $T$ 组测试数据。

每组数据第一行包含两个整数 $n,m$。

接下来 $m$ 行，每行包含三个整数 $t,x,y$，用来描述一条边的信息，其中 $t$ 表示边的状态，如果 $t=0$，则表示边是无向边，如果 $t=1$，则表示边是有向边。$x,y$ 表示这条边连接的两个端点，如果是有向边则边的方向是从 $x$ 指向 $y$。

保证图中没有重边（给定了 $(x,y)$，就不会再次出现 $(x,y)$ 或出现 $(y,x)$）和自环（不会出现 $x=y$ 的情况）。

输出格式

对于每组数据，如果无法构造出有向无环图，则输出一行 NO。

否则，先输出一行 YES，随后 $m$ 行，每行包含两个整数 $x,y$，用来描述最终构造成的有向无环图中的每条边的具体方向（$x$ 指向 $y$），边的先后顺序随意。

注意，已经确定方向的边，不能更改方向。

如果答案不唯一，输出任意合理方案均可。

数据范围

对于前三个测试点，$1≤n,m≤10$。

对于全部测试点，$1≤T≤20000，2≤n≤2×10^5，1≤m≤min(2×10^5,\frac{n(n−1)}{2}),0≤t≤1,1≤x,y≤n$。

保证在一个测试点中，所有 $n$ 的和不超过 $2×10^5$，所有 $m$ 的和不超过 $2×10^5$。

输入样例

4
3 1
0 1 3
5 5
0 2 1
1 1 5
1 5 4
0 5 2
1 3 5
4 5
1 1 2
0 4 3
1 3 1
0 2 3
1 2 4
4 5
1 4 1
1 1 3
0 1 2
1 2 4
1 3 2

输出样例

YES
3 1
YES
2 1
1 5
5 4
2 5
3 5
YES
1 2
3 4
3 1
3 2
2 4
NO

题解

拓扑排序

题目含义，给你一个无自环、无重边的图，图中某些边是有向边，某些是无向边，要求你将无向边确定为有向边，使整个图为一个有向无环图。

则我们先考虑用拓扑排序检测整个包含有向边的图是否存在环，若不存在环，则只要将无向边按照拓扑序列的先后顺序连接边即可，输出 yes；否则将其，否则输出 NO。

代码

#include<bits/stdc++.h>
using namespace std;

const int N = 2e5 + 5, M = 2e5 + 5;
int T, n, m, tot, k;
int head[N], ver[M], Next[M], pos[N], deg[N];
vector<int> ans;
struct Edge{
    int a, b;
} e[M];

void add(int x, int y){
    ver[++tot] = y;
    Next[tot] = head[x];
    head[x] = tot;
}

bool topSort() {
    //广搜求拓扑序列
    ans.clear();
    queue<int> q;
    for (int i = 1; i <= n; i++) {
        if (deg[i] == 0) q.push(i);     //入度为0则入队
    }

    while (q.size()) {
        auto now = q.front();
        q.pop();
        ans.push_back(now);     //出队即进入答案序列

        for (int i = head[now]; i; i = Next[i]) {   //遍历当前节点的所有邻接节点
            int y = ver[i];
            if (--deg[y] == 0) q.push(y);   //入度为0则入队
        }
    }
    
    return ans.size() == n;   //出队序列长度等于节点个数
}

int main(){
    cin >> T;
    while(T--){
        memset(head, 0, (n + 1) * 4);
        memset(deg, 0, (n + 1) * 4);
        scanf("%d%d", &n, &m);
        tot = k = 0;
        for(int i = 1, t, x, y; i <= m; i++){
            scanf("%d%d%d", &t, &x, &y);
            if(!t) e[++k] = {x, y}; //无向边
            else {  //有向边
                add(x, y);
                deg[y]++;
            }
        }
        if(!topSort()) puts("NO");
        else {
            puts("YES");
            for(int x = 1; x <= n; x++){
                for(int j = head[x]; j; j = Next[j]){
                    printf("%d %d\n", x, ver[j]);
                }
            }
            
            for(int i = 0; i < n; i++) pos[ans[i]] = i;
            for(int i = 1; i <= k; i++){
                int a = e[i].a, b = e[i].b;
                if(pos[a] > pos[b]) swap(a, b);
                printf("%d %d\n", a, b);
            }
        }
    }
    
    return 0;
}