拓樸排序

有多個優先順序的排序

拓樸排序

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

struct cmp{
    bool operator()(int a, int b) {
        return a > b;
    }
};

int main(){
    int n;
    cin >> n;
    vector<vector<int>> adj(n+1);
    vector<int>inDegree(n+1,0);
    vector<int>result;
    priority_queue<int, vector<int>, cmp> pq;
    for(int i=1;i<=n;++i){
        int m;
        cin >> m;
        for(int j=0;j<m;++j){
            int x;
            cin >> x;
            adj[x].push_back(i);
            inDegree[i]++;
        }
    }
    //------------------------------
    for(int i=1;i<=n;++i){
        if(inDegree[i]==0){
            pq.push(i);
        }
    }
    //------------------------------
    while(!pq.empty()){
        int u = pq.top();
        pq.pop();
        result.push_back(u);
        for(int v : adj[u]){
            inDegree[v]--;
            if(inDegree[v]==0){
                pq.push(v);
            }
        }
    }
    //-----------------------------
    for (int i = 0; i < result.size(); i++) {
        cout << result[i] << " ";
    }
    cout << endl;
}