30分求助

B3644 【模板】拓扑排序 / 家谱树

hhy8399 @ 2024-10-06 18:49:18

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1e6 + 5;

int n,k,in[MAXN];
vector <int > g[MAXN];

void top_sort()
{
    queue<int > top;
    for(int i = 1;i <= n;i++)
    {
        if(in[i] == 0)
        {
            top.push(i);
        }
    }
    while(!top.empty())
    {
        int u = top.front();
        top.pop();
        printf("%d ",u);
        for(int i = 0;i < (int)g[u].size();i++)
        {
            in[g[u][i]] --;
            if(in[g[u][i]] == 0)
            {
                top.push(g[u][i]);
            }
        }
    }
}

int main()
{
    scanf("%d",&n);
    for(int i = 1;i <= n;i++)
    {
        scanf("%d",&k);
        while(k)
        {
            g[i].push_back(k);
            scanf("%d",&k);
            in[k] ++;
        }
    }
    top_sort();
    return 0;
} 

by __zyy_wgcs__ @ 2024-10-06 18:54:44

in[k] ++;移到g[i].push_back(k);上面,不然就有可能把0当做一个结点


by hhy8399 @ 2024-10-06 18:57:52

@__zyy_wgcs__ 谢谢


|