题解 | #【模板】拓扑排序#

这个题不标准，说好拓扑排序序列不唯一时输出任一，结果只给了唯一值，需用queue存储，入度为0的顶点入队，求拓扑排序序列时队头出队加入序列。

#include<iostream>
#include<vector>
#include<queue>
using namespace std;

class Solution {
public:

    void Topu(int n, int m, vector<pair<int,int>>& e) {
        //根据边转化为类似图的邻接表存储方式，同时统计各顶点的入度，入度为0的点存储在一个向量中
        vector<int> ind(n+1,0);
        queue<int> pq;
        vector<vector<int>> graph(n+1);//graph[i]存储顶点i邻接的所有顶点j，即为j构成的集合
        vector<int> ss;
        for(auto i:e){
            graph[i.first].push_back(i.second);
            ind[i.second]++; //入度+1
        }
        for(int i=1;i<=n;i++){
            if(ind[i]==0)
                pq.push(i);  //入度为0的顶点
        }
        while(!pq.empty()){
            int t=pq.front();
            pq.pop();
            ss.push_back(t);
            for(auto i:graph[t]){
                ind[i]--;
                if(ind[i]==0) pq.push(i);
            }
        }
        if(ss.size()!=n)
            cout<<-1;
        else
            {
                for(int i=0;i<n;i++){
                    if(i==0)
                    cout<<ss[i];
                    else
                     cout<<" "<<ss[i];
                }
            }

    }
};

int main(){

int n,m;
cin>>n>>m;
vector<pair<int,int>> e;
int a,b;
for(int i=0;i<m;i++){
   cin>>a>>b;
   e.emplace_back(a,b);
}

Solution().Topu(n,m,e);
return 0;
}