Cod sursa(job #1357101)

Utilizator dragos_musanMusan Dragos dragos_musan Data 23 februarie 2015 19:29:17
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.81 kb
#include<fstream>
#include<vector>
#include<queue>

using namespace std;

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

const int NMAX = 50001;

int n,m;
vector <int> v[NMAX];
int pred[NMAX];
queue <int> q;

void citire()
{
    int x,y;

    f >> n >> m;

    for(int i = 1; i<=m; i++)
    {
        f >> x >> y;
        v[x].push_back(y);
        pred[y]++;
    }
}

int main()
{
    int i,x;

    citire();

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

    while(!q.empty())
    {
        x = q.front();
        q.pop();
        g << x << ' ';

        for(i = 0; i < v[x].size(); i++)
        {
            pred[v[x][i]]--;
            if(pred[v[x][i]] == 0)
                q.push(v[x][i]);
        }
    }

    return 0;
}