有向图的堆排序

CPP 刷题王 2023-02-17 21:09:50 0
{{ vote && vote.total.up }}

共 3 条回复

root 站长
#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 10;

int n, m;
int h[N], e[N], ne[N], idx;

int in[N];
int q[N];

void add(int a, int b)
{
    ne[idx] = h[a];
    e[idx] = b;
    h[a] = idx++;
}

int topsort()
{
    int hh = 0, tt = -1;
    
    for (int i = 1; i <= n; i ++ )
    {
        if(in[i] == 0)
            q[++ tt] = i;
    }
    
    while (hh <= tt)
    {
        int t = q[hh ++];
        for (int i = h[t]; i != -1; i = ne[i])
        {
            int j = e[i];
            if (--  in[j] == 0)
                q[++ tt] = j;
        }
    }
    return tt != n - 1;
}
int main()
{
    cin >> n >> m;
    memset(h, -1, sizeof h);
    for (int i = 1; i <= m; i ++ )
    {
        int a, b;
        cin >> a >> b;
        add(a, b);
        in[b] ++;
    }
    
    if (topsort()) puts("-1");
    else 
        for (int i = 0; i < n; i ++ )
            cout << q[i] << " ";
    return 0;
}
jsq 蒟蒻

???

tctm103

神马情况?