Cod sursa(job #2119427)

Utilizator andreibudoiAndrei Budoi andreibudoi Data 1 februarie 2018 10:26:59
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.84 kb
#include <iostream>
#include <fstream>
#include <vector>

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

vector <int> v[50002];
int grad[50002];
int sol[50002];
int n,m;

int main()
{
    int i,ii,j,x,y,ind=1;
    f>>n>>m;
    for(i=1; i<=m; i++)
    {
        f>>x>>y;
        v[y].push_back(x);
        grad[x]++;
    }
    for(i=1; i<=n; i++)
    {
        if(grad[i]==0)
        {
            sol[ind]=i;
            ind++;
        }

    }
    for(ii=1; ii<ind; ii++)
    {
        i=sol[ii];

        for(j=0; j<v[i].size(); j++)
        {
            grad[v[i][j]]--;
            if(grad[v[i][j]]==0)
            {
                sol[ind]=v[i][j];
                ind++;
            }
        }




    }
    for(i=n;i>=1;i--)
    g<<sol[i]<<" ";


    return 0;
}