Cod sursa(job #2035578)

Utilizator Victor24Vasiesiu Victor Victor24 Data 9 octombrie 2017 17:24:29
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.92 kb
#include <fstream>
#include <bits/stdc++.h>
using namespace std;

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

vector < int > v[50005];

queue < int > q;

int i, j, n, grad[50005], m, rsp[50005], a, b, cur, loc;

int main ()
{
    f>>n>>m;

    for ( i = 1; i <= m ; i++ )
    {
        f>>a>>b;

        v[a].push_back(b);

        grad[b]++;

    }

    for ( i = 1; i <= n ; i++ )
    {
        if ( grad[i] == 0 )
        {
            q.push(i);
        }
    }

    while ( !q.empty() )
    {
        cur = q.front();
        rsp[++loc] = cur;
        for ( i = 0 ; i < v[cur].size() ; i++ )
        {
            grad[ v[cur][i] ]--;

            if ( grad[ v[cur][i] ] == 0 )
            {
                q.push( v[cur][i] );
            }

        }

        q.pop();

    }

    for ( i = 1; i <= loc ; i++ )
    {
        g<<rsp[i]<<" ";
    }

    return 0;
}