无语了,调了一下午,结果边没开多。
还是套模板,但是边权需要多开一点点,他有别于模板,模板是点对点之间的边权,边不会那么多,但是这里一样。用邻接表去构建的时候,会产生一对多的情况
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
//接下来 n 行,第 i 行描述第 i 个人的孩子;
//每行最后是 0 表示描述完毕。
//每个人的编号从1到n。
const int N=110,M=110*110/2;
int h[N],e[M],ne[M],idx;
int d[N];
//vector<int> res;//最后输出在序列
int top[N];
int cnt;
int n;
void add(int a,int b){
e[idx]=b;
ne[idx]=h[a];
h[a]=idx++;
}
void topsort(){
queue<int> q;
for(int i=1;i<=n;i++){
if(d[i]==0) q.push(i);//就是把数字拿出来(其实就是拿出了数字的索引)
}
while(q.size()){
auto t=q.front();
//遍历链表
//res.push_back(t);
top[cnt++]=t;
q.pop();
for(int i=h[t];~i;i=ne[i]){
// 把i的出度找出来,如果删除入度,且度为0,那么就是拓扑序列
int j=e[i];
d[j]--;
if(d[j]==0) q.push(j);
}
}
}
int main(){
cin>>n;
memset(h,-1,sizeof h);
for (int i = 1; i <= n; i ++ ){
int son;
while (cin >> son, son)
{
add(i, son);
d[son] ++ ;
}
}
topsort();
//题目的测试数据肯定是满足了拓扑顺序
//for(auto c:top) cout<<c<<' ';
for(int i=0;i<n;i++) cout<<top[i]<<' ';
return 0;
}