Cod sursa(job #1342415)

Utilizator ilenitudorIleni Tudor ilenitudor Data 13 februarie 2015 23:30:02
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.94 kb
#include <iostream>
#include<fstream>
#include<cstring>
#include<vector>
using namespace std;

ifstream fin("sortaret.in");
ofstream fout("sortaret.out");

using namespace std;

#define maxx 50010
#define pb push_back

vector<int> G[maxx];
int n,m,grd[maxx];
int sol[maxx];
void solve()
{
    vector<int>::iterator it;
    for(int i=1 ; i<=n; i++)
    if(grd[i] ==0 )
       sol[++sol[0]] = i;
    for(int i=1 ; i<=n ; i++)
    {
        int x = sol[i];
        for(it = G[x].begin() ; it != G[x].end() ; ++it)
            {
             grd[*it]--;
             if(grd[*it] == 0)
                sol[++sol[0]] = *it;
            }
    }
}
void read()
{
    fin>>n>>m;
    for(int i=1;i<=m;i++)
    {
     int x,y;
     fin>>x>>y;
     G[x].pb(y);
     grd[y]++;
    }
}
void print()
{
    for(int i=1;i<=n;i++)
        fout<<sol[i]<<" ";
}
int main()
{
    read();
    solve();
    print();
    return 0;
}