拓扑排序

525

拓扑排序的原理就是在队列里面操作,先将图存储起来,然后每次选择入度为0的点作为开始,每次选择这个入度为0的点作为开始,逐步释放以他指向的点,如果被指向的点的入度减为0,也加入队列之中,加入队列的元素就是其中一个拓扑排序.同时也可用来检测这个有向图是否形成环

#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5+10;
int ind[maxn];//表示每个结点的入度
int n,m;
map<int, vector <int> > mp;
vector<int> va;
// 进行拓扑排序
void aov()
{
    int t = 0;
    queue<int> q;
    for(int i = 1;i<=n;i++)
    {
        if(ind[i]==0)
        {
            t++;
            q.push(i);//入度为0的放进去
            va.push_back(i);
        }
    }
    while(!q.empty())
    {
        int tp = q.front();
        q.pop();
        // 拿出该节点可以到达的点
        for(int vtx: mp[tp])
        {
            ind[vtx]--;
            if(ind[vtx]==0)
            {
                q.push(vtx);
//                 cout << vtx <<" ";
                va.push_back(vtx);
                t++;
            }
        }
    }
    if(t!=n) {
        cout << -1;
        return;
    }
    
    for(int i = 0;i<n;i++)
    {
        cout << va[i];
        if(i!=n-1) cout << " ";
    }
}

int main()
{
    cin >> n >> m;
    for(int i = 0;i<m;i++)
    {
        int a,b;cin >> a >> b;
        // a指向b b的入度增加
        mp[a].push_back(b);
        ind[b]++;
    }
    aov();
    return 0;
}