Untitled

mail@pastecode.io avatar
unknown
c_cpp
9 days ago
1.2 kB
1
Indexable
Never
#include <bits/stdc++.h>
using namespace std;
#define ll long long

void solve()
{
    int n;
    int m;
    cin>>n;cin>>m;
    vector<vector<int>>adj(n);
    vector<int>indegree(n);
    for(int i=0;i<m;i++){
        int a;
        int b;
        cin>>a;
        cin>>b;
        adj[a-1].push_back(b-1);
        indegree[b-1]++;
    }
    priority_queue<int ,vector<int>,greater<int>>q;
    vector<int>topo;

    for(int i=0;i<n;i++){
        if(indegree[i]==0){
            q.push(i);
        }
    }
    vector<pair<int,int>>ans;
        while(!q.empty()){
            int node=q.top();
            topo.push_back(node);
            q.pop();
            for(auto it:adj[node]){
                indegree[it]--;
                if(indegree[it]==0){
                q.push(it);
                }
            }
        }
    int sz=topo.size();
    for(int i=0;i<sz;i++){
        ans.push_back({topo[i],i+1});
    }
    sort(ans.begin(),ans.end());
    for(auto&it:ans){
        cout<<it.second<<" ";
    }
    
}

int main()
{
    int t=1;
    // cin >> t;
    while (t--)
    {
        solve();
    }
    return 0;
}
Leave a Comment