思路
找到所有入度为零的点,然后消除其子节点的入度,再把入度为零的点塞入队列中
为什么可以这么做呢?
一个点能弹出队列,其父节点一定比他先入队,以此类推。。
代码
#include<bits/stdc++.h>
using namespace std;
vector<int> G[100005];
int in[100005]={0};
int main()
{
int n;
cin>>n;
for(int i=1;i<=n;i++)
{
int x;
while(scanf("%d",&x)&&x!=0)
{
G[i].push_back(x);
in[x]++;
}
}
queue<int> q;
for(int i=1;i<=n;i++)
if(!in[i]) q.push(i);
while(!q.empty())
{
int now=q.front();
q.pop();
for(int i=0;i<G[now].size();i++)
{
int next=G[now][i];
in[next]--;
if(!in[next])q.push(next);
}
printf("%d ",now);
}
return 0;
}
标签:加强版,int,入度,100005,T397291,模板
From: https://www.cnblogs.com/pure4knowledge/p/17928882.html