Cod sursa(job #1037475)

Utilizator gorgorothPurice Ciprian gorgoroth Data 20 noiembrie 2013 11:58:03
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.66 kb
#include <fstream>
#include<vector>
using namespace std;
ifstream f("sortaret.in");
ofstream g("sortaret.out");
vector<long long>b[100000];
int n,m;
long long lg[100000],di[100000],c[100000];
int main()
{
    int i,x,y,j,u,w,z,p;
f>>n>>m;
while (f>>x>>y)
{
    b[x].push_back(y);
    di[y]++;
}
for(i=1;i<=n;i++)
    lg[i]=b[i].size();
u=0;
p=1;
for(i=1;i<=n;i++)
if(di[i]==0)
    {
        u++;
        c[u]=i;
    }
while(p<=u)
{
    z=c[p];
    p++;
    for(j=0;j<lg[z];j++)
    {
        w=b[z][j];
        di[w]--;
    if(di[w]==0)
    {
        u++;
        c[u]=w;
    }
    }
}
   for(i=1;i<=n;i++)
   g<<c[i]<<' ';
}