Cod sursa(job #1419717)

Utilizator andreii1Ilie Andrei andreii1 Data 16 aprilie 2015 11:23:00
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.66 kb
#include <cstdio>
#include <vector>
using namespace std;

vector<int> v[50001];
int n,m,viz[50001],sol[50001],nr,b[50001];

void df(int k)
{
    int i;
    viz[k]=1;
    for(i=0;i<b[k];i++)
        if(viz[v[k][i]]==0)df(v[k][i]);
    sol[++nr]=k;
}

int main()
{
    int i,x,y;
    FILE *f=fopen("sortaret.in","r");
    FILE *g=fopen("sortaret.out","w");
    fscanf(f,"%d %d",&n,&m);
    for(i=1;i<=m;i++)
    {
        fscanf(f,"%d %d",&x,&y);
        v[x].push_back(y);
        b[x]++;
    }
    for(i=1;i<=n;i++)
        if(!viz[i]) df(i);
    for(i=1;i<=n;i++)fprintf(g,"%d ",sol[n-i+1]);
    fclose(f);
    fclose(g);
    return 0;
}