Cod sursa(job #1963270)

Utilizator fluture.godlikeGafton Mihnea Alexandru fluture.godlike Data 12 aprilie 2017 13:36:00
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.89 kb
#include <cstdio>
#include <algorithm>
#include <vector>
#include <queue>

#define in "sortaret.in"
#define out "sortaret.out"
#define NMAX (50000 + 7)
#define pb push_back

using namespace std;
int n, m, a, b, inp[NMAX];
vector <int> adj[NMAX];
queue <int> srt;

int main()
{
    freopen(in, "r", stdin);
    freopen(out, "w", stdout);
    scanf("%d %d", &n, &m);
    for(int i = 1; i<= m; ++i)
    {
        scanf("%d %d", &a, &b);
        adj[a].pb(b);
        inp[b] ++;
    }
    for(int i = 1; i<= n; ++i) if(inp[i] == 0) srt.push(i);
    while(!srt.empty())
    {
        int top = srt.front();
        srt.pop();
        printf("%d ", top);
        int sze = adj[top].size();
        for(int i = 0; i< sze; ++i)
        {
            inp[adj[top][i]] --;
            if(inp[adj[top][i]] == 0) srt.push(adj[top][i]);
        }
    }
    printf("\n");
    return 0;
}