Cod sursa(job #2926035)

Utilizator ancaoxoxSfia Anca ancaoxox Data 16 octombrie 2022 19:17:06
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.72 kb
#include <iostream>
#include <vector>
#include <fstream>

#define MAXN 50100
using namespace std;

vector<int> v[MAXN];
int n, m, out[MAXN], in[MAXN], l[MAXN], cnt;

ifstream f("sortaret.in");
ofstream g("sortaret.out");

int main()
{
    int a, b;
    f >> n >> m;

    for (int i=1; i<=m; i++)
    {f >> a >> b;
    out[a]++;
    v[b].push_back(a);
    }



    for (int i=1; i<=n; i++)
    if (out[i]==0)
    l[++l[0]]=i;


    for (int i=1; i<=n; i++)
    {
        int x=l[i];
        for (int j=0; j<v[x].size(); j++)
        {out[v[x][j]]--;
        if (out[v[x][j]]==0) l[++l[0]]=v[x][j];
        }

    }


    for (int i=n; i>=1; i--)
        g << l[i] << " ";

    return 0;
}