Cod sursa(job #1632794)

Utilizator GeraltMirea Radu Geralt Data 6 martie 2016 10:56:30
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.79 kb
#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

vector <int> v[50001],vt[50001],con[1000];
int viz[50001],q[1000],gre[1000],n,m;


fstream f("sortaret.in");
ofstream g("sortaret.out");


void sol(){
int i,x,j,l=1;

for(i=1;i<=n;i++)
    if(gre[i]==0) q[l++]=i;;

for(i=1;i<=n;i++)
{ x=q[i];

for(j=0;j<v[x].size();j++)
{
    gre[v[x][j]]--;
    if(gre[v[x][j]]==0) q[l++]=v[x][j];
}
}
}

/*void DF(int i){
int j;

sign[si][i]=1;

for(j=0;j<a[i].size();j++){
    if(viz[a[i][j]]==0){
            viz[a[i][j]]=1;
        DF(a[i][j]);

    }
}

}*/


int main()
{ int x,y,i,j;

    f>>n>>m;

    for(i=1;i<=m;i++)
    f>>x>>y, v[x].push_back(y),gre[y]++;

sol();

for(i=1;i<=n;i++)
    g<<q[i]<<" ";



    return 0;
}