B3644 【模板】拓扑排序 / 家谱树 超级详细讲解

家谱树 超级详细讲解"/>

B3644 【模板】拓扑排序 / 家谱树 超级详细讲解

#include<bits/stdc++.h>
using namespace std;
int n;const int N=111,M=1e6+1;//此处范围设定尤其注意区分
int q[N];//队列 从对头输出度为0的元素 队尾输入度为0元素
int deg[N];//以某点发出的边int e[M],ne[M],h[N],idx;//e 代表值 ne代表指向的下一个点 h相当于一个槽 放临接表 idx代表下一个可用的点void  add(int x,int y)
{e[idx]=y;ne[idx]=h[x];h[x]=idx++;
}//h里是上面的值 idx是他下面的链  void topsort()
{int hh=0,tt=0;for(int i=1;i<=n;i++)if(!deg[i]) q[tt++]=i;//入度为0的入队while(hh<=tt){int t=q[hh++];//取出在队头入度为0的元素for(int i=h[t];i;i=ne[i])//遍历每一个值下面的表{int j=e[i];if(--deg[j]==0)//将i->j的边删除{q[tt++]=j;//将0度入队}}}
}int main()
{cin>>n;int m;for(int i=1;i<=n;i++){while(cin>>m&&m)//不断读入 直到为0{add(i,m);//I->m的边deg[m]++;//边++}}topsort();for(int i=0;i<n;i++)cout<<q[i]<<" ";
}