【模板】拓扑排序

【家谱树】

拓扑排序也是可以解决自环、出入顺序的问题。

什么是拓扑排序？

定义： 由最外层节点，沿着边向内走的一个一条路径称为拓扑排序。（个人定义）

方法： 从入度为0的点开始跑跑图，每跑一条边就让该边的另一个节点入度减少1，当一个节点的入度为0的时候，这个节点就在最外层了，就该让这个节点去跑图。

性质：

1. 有向无环图一定是拓扑序列,有向有环图一定不是拓扑序列。
2. 无向图没有拓扑序列。

图解

Code

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+12;
int head[N],ans[N],cnt,tot;
int t[N],n;

struct {
  int to,nex;
}edge[N];

void addedge(int u,int v)
{
  cnt++;
  edge[cnt]={v,head[u]};
  head[u]=cnt;
}
queue<int>q;

void f()
{
  while(q.size())
  {
    int y=q.front();
    q.pop();
    for(int i=head[y];i;i=edge[i].nex)
    {
      int x=edge[i].to;
      t[x]--;
      if( !t[x] )
      {
        ans[++tot]=x;
        q.push(x);
      }
    }


  }


}


int main(){
  cin>>n;
  for(int i=1;i<=n;i++)
  {
    int x;
    while( scanf("%d",&x) )
    {
      if( !x ) break;
      addedge(i,x);
      t[x]++;
    }
  }
  for(int i=1;i<=n;i++)
  {
    if( !t[i] ) {ans[++tot]=i,q.push(i);}
  }

  f();
  for(int i=1;i<=n;i++)
  {
    cout<<ans[i]<<" ";
  }


}