Cod sursa(job #2628480)

Utilizator pregoliStana Andrei pregoli Data 16 iunie 2020 09:06:12
Problema Sortare topologica Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.95 kb
#include <bits/stdc++.h>
#define newline '\n'
using namespace std;
ifstream fin("sortaret.in");
ofstream fout("sortaret.out");
///***********************
const int NMAX = 5e4 + 3;
int ans[NMAX], deg[NMAX], ansSz;
vector<int> graph[NMAX];
int n, m;

void read()
{
    fin >> n >> m;
    for (int i = 0; i < m; i++)
    {
        int a, b;
        fin >> a >> b;
        deg[b]++;
        graph[a].push_back(b);
    }
}

void solve()
{
    for (int i = 1; i <= n; i++)
        if (!ans[i])
            ans[++ansSz] = i;
    for (int i = 1; i <= n; i++)
    {
        int e = ans[i];
        for (auto it : graph[e])
        {
            deg[it]--;
            if (!deg[it])
                ans[++ansSz] = it;
        }
    }
}

void display()
{
    for (int i = 1; i <= n; i++)
        fout << ans[i] << ' ';
    fout << newline;
}

int main()
{
    read();
    solve();
    display();
    fout.close();
    return 0;
}