526互联

Acwing 3696-构造有向无环图 / 拓扑排序 / 指定无向边的方向，让其和有向边一起构造成一个拓扑图

发布时间 2023-04-23 21:01:52作者: 妃即

Acwing 3696-构造有向无环图
开始想了半天没想明白，后来突然想到这个题目这个名称，或许是一个模板题。我不知道是不是模板题，但我当模板题记下来，因为我理解不了。

操作：

1. 读边时有向边指向的点入度增加，无向边入度都为 0， 用结构体存下所有无向边
2. 进行一次 top_sort，只要点入度为 0，就加入队列，不管这个入度为 0 的点是有向边的点还是无向边的点，且给依次出队的点标序 (pos[t] = order ++ )
3. 如果 top_sort 后出队的点的总数为总点数，则可以构造一个有向无环图，然后才进行下面的 4，5
4. 枚举所有点，输出有向边的点的所有边
5. 枚举存放无向边的结构体的所有边，对于每条无向边里的 a，b两点，pos 小的先输出，pos 大的后输出

#include <iostream>
#include <cstring>
#include <queue>

using namespace std;

const int N = 2e5 + 10, M = N;

int e[M], ne[M], h[N], idx;
int d[N], pos[N];
int n, m, T;

int u;
struct node
{
    int a, b;    
}edge[M]; // 存无向边

void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;    
}

int top_sort()
{
    queue<int>q;
    
    for (int i = 1; i <= n; i ++ )
       if (d[i] == 0) q.push(i);
    
    int order = 0, sum = 0;
    while (q.size())
    {
        
        int t = q.front();
        q.pop();
        
        sum ++ ;
        pos[t] = order ++ ;
        
        for (int i = h[t]; i != -1; i = ne[i])
        {
            int j = e[i];
            
            d[j] -- ;
            
            if (d[j] == 0) q.push(j);
        }
    }
    
    return sum == n;
}

int main()
{
    cin >> T;
    while (T -- )
    {
        idx = 0, u = 0;
        memset(h, -1, sizeof h);
        memset(d, 0, sizeof d);
        
        scanf("%d%d", &n, &m);
        while (m -- )
        {
            int type, a, b;
            scanf("%d%d%d", &type, &a, &b);
            
            if (type == 1) add(a, b), d[b] ++ ;
            else edge[u ++ ] = {a, b};
        }
        
        int t = top_sort();
        
        if (t == 0) printf("NO\n");
        else {
            printf("YES\n");
            
            for (int k = 1; k <= n; k ++ ) 
                 for (int i = h[k]; i != -1; i = ne[i])
                      printf("%d %d\n", k, e[i]);
                      
            for (int i = 0; i < u; i ++ )
            {
                int a = edge[i].a, b = edge[i].b;
                
                if (pos[a] < pos[b]) printf("%d %d\n", a, b);
                else printf("%d %d\n", b, a);
            }
        }
    }
    
    return 0;
}