Cod sursa(job #960380)

Utilizator alex_bucevschiBucevschi Alexandru alex_bucevschi Data 10 iunie 2013 12:58:51
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.66 kb
#include <fstream>
#include <vector>
#define N 50001
using namespace std;
ifstream fin("sortaret.in");
ofstream fout("sortaret.out");
vector <int> v[N];
int n,m,x,y,i,j,DR,g[N],sol[N];
int main()
{
    fin>>n>>m;
    for(;m;m--)
    {
        fin>>x>>y;
        v[x].push_back(y);
        g[y]++;
    }
    for(DR=0,i=1;i<=n;i++)
        if(!g[i])
            sol[++DR]=i;
    for(i=1;DR<n;i++)
    {
        for(vector<int>::iterator it=v[i].begin();it!=v[i].end();it++)
        {
            g[*it]--;
            if(!g[*it])
                sol[++DR]=*it;
        }
    }
    for(i=1;i<=n;i++)
        fout<<sol[i]<<" ";
    return 0;
}