拓扑排序

1.什么是拓扑排序

　　拓扑排序就是对有向无环图（DAG）上的一些点的编号进行排序，使得图中每条边的起点都比终点的位置要靠前

前置知识：度

一个点连着的边的数量，称为该点的度。其中由该点出发的称为出度，到达该点的称为入度。

2.如何实现

　　算法过程：

先统计所有点的入度，分离出入度为0的点，将其存到答案队列中，然后将这个点有边指向的所有的点的入度都减一
重复上述操作，直到没有点入度为零
如果还有点入度不为零，就说明有环，则问题无解

拓扑排序

比如这个图

拓扑排序

我们发现点1入度为0，所以分离点1，并对其他点的入度进行调整

拓扑排序

此时我们发现点2和4入度为0，那么我们先分离点2，调整入度

拓扑排序

继续分离

拓扑排序

有环的情况：

拓扑排序

我们发现无论如何都没有点的入度为1，此时拓扑序无解

代码：

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

const int MAXN=9999999;

int head[MAXN],to[MAXN],nxt[MAXN],in[MAXN],cnt;
int ans[MAXN],nodecnt;

inline void add(int u,int v) 
{
    cnt++;
    to[cnt]=v;
    nxt[cnt]=head[u];
    head[u]=cnt;
}

int n,m;

int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)
    {
        int start,end;
        scanf("%d%d",&start,&end);
        add(start,end);
        in[end]++;
    }
    priority_queue<int,vector<int>,greater<int> > q;
    for(int i=1;i<=n;i++)
    {
        if(!in[i]) q.push(i);
    }
    while(!q.empty())
    {
        int top=q.top();
        q.pop();
        ans[++nodecnt]=top;
        for(int e=head[top];e;e=nxt[e])
        {
            in[to[e]]--;
            if(!in[to[e]]) q.push(to[e]);
        }
    }
    if(nodecnt!=n) printf("No Solution");
    else 
    {
        for(int i=1;i<=nodecnt;i++)
        {
            printf("%d ",ans[i]);
        }
    }
    
}

前置知识：度

相关推荐