1 条题解

  • 0
    @ 2025-12-5 12:09:47

    用到了优先队列以保证字典序最小!!!

    #include<iostream>
    #include<vector>
    #include<stack>
    #include <queue>
    using namespace std;
    
    vector<vector<int>> graph;
    vector<int> ans;
    priority_queue<int, vector<int>, greater<int>> s;
    int* indegree;
    int n,m;
    
    int main(){
        cin>>n>>m;
        graph.resize(n+1);
        indegree=new int[n+1]();
        
        for(int i=0;i<m;i++)
        {
            int u,v;
            cin>>u>>v;
            graph[u].push_back(v);
            indegree[v]++;
        }
        
        for(int i=1;i<=n;i++)
        {
            if(indegree[i]==0) s.push(i);
        }
        
        int count=0;
        while(!s.empty())
        {
            int u=s.top();
            s.pop();
            ans.push_back(u);
            count++;
            for(int v:graph[u])
            {
                indegree[v]--;
                if(indegree[v]==0) s.push(v);
            }
        }
    
        if(count!=n) cout<<-1<<"\n";
        else
        {
            for(int i:ans)
            {
                cout<<i<<" ";
            }
        }
        delete[] indegree;
        return 0;
    }
    
    • 1

    信息

    ID
    53
    时间
    1000ms
    内存
    256MiB
    难度
    3
    标签
    递交数
    23
    已通过
    9
    上传者