拓扑排序

#include <iostream>
#include <vector>
#include <cstring>

using namespace std;

const int N=1e5+5;

int h[N], e[N], ne[N], indegree[N], idx;

int head, tail, queue[N];


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

void tpSort(int n){
    head = 0; tail = -1;
    for (int i=1; i<=n; i++){
        if (indegree[i]==0) queue[++tail] = i;
    }

    while (head<=tail){
        int node = queue[head++];
        for (int i = h[node]; i != -1; i =ne[i]){
            int j = e[i];
            indegree[j]--;
            if (indegree[j]==0) queue[++tail] = j;
        }
    }
    if (tail != n-1) cout << -1;
    else {
        for (int i=0; i<n; i++) cout<<queue[i]<<" ";
    }
}

int main(){
    int n, m, x, y;
    cin >> n >> m;
    memset(h, -1, sizeof h);
    for (int i=0; i<m; i++) {
        cin >> x >> y;
        add(x, y);
        indegree[y] ++;
    }
    tpSort(n);
    return 0;
}

 

上一篇:1171. 距离(lca)


下一篇:动态规划_树形DP