Java教程

拓扑排序

本文主要是介绍拓扑排序,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

848. 有向图的拓扑序列

题目链接
https://www.acwing.com/problem/content/850/

解析
要掌握拓扑排序的基本思路:每次找到入度为0的点加入队列,可以用数组存答案,根据加入队列的数的个数可以判断是否可以进行拓扑排序。

Ac代码

点击查看代码
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>

using namespace std;

const int N = 1e5 + 10;

int h[N], e[N], ne[N], idx;
int n, m;
int du[N], ans[N], x;

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

bool topsort()
{   
    queue<int> q;
    for(int i = 1; i <= n; i ++)
        if(du[i] == 0) q.push(i);
    
    while(q.size()){
        auto t = q.front(); q.pop();
        ans[x ++] = t;
        for(int i = h[t]; i != -1; i = ne[i]){
            int j = e[i];
            du[j] --;
            if(!du[j]){
                q.push(j);
            }
        }
    }
    if(x < n) return false;
    return true;
}

int main()
{
    scanf("%d%d", &n, &m);
    memset(h, -1, sizeof h);
    while(m --){
        int a, b;
        scanf("%d%d", &a, &b);
        add(a, b);
        du[b] ++;
    }
    
    if(!topsort()){
        printf("-1\n");
    }
    else{
        for(int i = 0; i < x; i ++) printf("%d ", ans[i]);
        puts("");
    }
    
    return 0;
}
这篇关于拓扑排序的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!