T397291 【模板】拓扑排序(加强版)

发布时间 2023-12-26 17:29:39作者: 纯粹的

原题链接

思路

找到所有入度为零的点,然后消除其子节点的入度,再把入度为零的点塞入队列中

为什么可以这么做呢?
一个点能弹出队列,其父节点一定比他先入队,以此类推。。

代码

#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;
}