Cod sursa(job #1645927)

Utilizator LipanmateiLipan Radu-Matei Lipanmatei Data 10 martie 2016 14:23:11
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.01 kb
#include <iostream>
#include <fstream>
#include <vector>

#define Nmax 50005
using namespace std;
ifstream fin("sortaret.in");
ofstream fout("sortaret.out");

vector < int > v[Nmax];
int n,m,k,gr[Nmax],poz[Nmax];


void sortare()
{
    //pun nodurile de grad 0 in coada
    for(int i=1;i<=n;i++)
        if(!gr[i])poz[++k]=i;
    //poz are rol atat de coada cat si de ordine finala a nodurilor
    for(int i=1;i<=n;i++)
    {
        int x=poz[i];
        for(vector <int > :: iterator ivector = v[x].begin();ivector!=v[x].end();ivector++)
        {
            //scad gradul cu fiecare vizitare
            gr[*ivector]--;
            //grad ajunge la 0 => i-am gasit pozitia
            if(!gr[*ivector])poz[++k]=*ivector;
        }
    }

}
void afis()
{
    for(int i=1;i<=n;i++)fout<<poz[i]<<'\n';
}
int main()
{
    fin>>n>>m;
    for(;m;m--)
    {
        int x,y;
        fin>>x>>y;
        v[x].push_back(y);
        gr[y]++;
    }
    sortare();
    afis();
    return 0;
}