搜索与图论——拓扑排序

有向图的拓扑排序就是图的宽度优先遍历的一个应用

有向无环图一定存在拓扑序列(有向无环图又被称为拓扑图),有向有环图一定不存在拓扑序列。无向图没有拓扑序列。

拓扑序列:将一个图排成拓扑序后,所有的边都是从前指向后的。

入度:有多少条边指向自己

出度:有多少条边指向别人

入度为0的点都可以排在最前边

#include<iostream>
#include<cstring>

using namespace std;

const int N = 100010;

int n, m;
int h[N], e[N], ne[N], idx;
int q[N];
int d[N]; //入度

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

bool topsort()
{
    int hh = 0, tt = -1;
    for(int i = 1; i <= n; i ++ )
    {
        if(!d[i]) q[ ++ tt] = i; \\入度为零的点推入队列
    }
    while(hh <= tt)
    {
        int t = q[hh ++ ];
        for(int i = h[t]; i != -1; i = ne[i])
        {
            int j = e[i]; //枚举t的所有出边j
            d[j] -- ; /删掉t -> j边,j的入度--
            if(d[j] == 0) q[ ++ tt] = j; //如果j的入度==0,推入队列
        }
    }
    return tt == n - 1; //如果队尾 == n - 1说明所有点都进过队列了,说明该图是一个有向无环图
}

int main()
{
    cin >> n >> m;
    memset(h, -1, sizeof h);
    while(m -- )
    {
        int a, b;
        cin >> a >> b;
        add(a, b);
        d[b] ++ ;
    }
    if(topsort())
    {
        for(int i = 0; i < n; i ++ ) cout << q[i] << " ";
    }
    else cout << -1 << endl;
    return 0;
}

相关推荐

  1. 算法——拓扑排序

    2024-04-05 06:38:01       46 阅读
  2. 洛谷——P1347 排序-拓扑排序)

    2024-04-05 06:38:01       59 阅读

最近更新

  1. docker php8.1+nginx base 镜像 dockerfile 配置

    2024-04-05 06:38:01       94 阅读
  2. Could not load dynamic library ‘cudart64_100.dll‘

    2024-04-05 06:38:01       101 阅读
  3. 在Django里面运行非项目文件

    2024-04-05 06:38:01       82 阅读
  4. Python语言-面向对象

    2024-04-05 06:38:01       91 阅读

热门阅读

  1. Docker搭建UniFi Controller

    2024-04-05 06:38:01       38 阅读
  2. Vben Admin实战-系统管理之用户管理-(第12节)

    2024-04-05 06:38:01       34 阅读
  3. Linux基础和进阶用法

    2024-04-05 06:38:01       41 阅读
  4. 求一个3*3的整型矩阵对角线元素之和

    2024-04-05 06:38:01       25 阅读
  5. 循环队列实现(python)

    2024-04-05 06:38:01       40 阅读
  6. 我对神经网络的一点理解

    2024-04-05 06:38:01       30 阅读
  7. 蓝桥杯 2023 省 B 洛谷P9242 接龙数列

    2024-04-05 06:38:01       37 阅读
  8. 7-43 哲哲打游戏

    2024-04-05 06:38:01       31 阅读
  9. 探索STM32串口通讯:打开硬件通道的魔法之门

    2024-04-05 06:38:01       36 阅读