Cod sursa(job #1130247)

Utilizator curajAndrei George curaj Data 28 februarie 2014 12:05:49
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.72 kb
#include <cstdio>
#include <vector>
using namespace std;

#define NMax 50001

vector<int> v[NMax];
int n,m,nr;
int viz[NMax],gr[NMax],postordine[NMax];

void DFS(int s)
{
    int i,e;
    viz[s]=1;
    e=v[s].size();
    for(i=0;i<e;i++) if(viz[v[s].at(i)]==0) DFS(v[s].at(i));
    postordine[++nr]=s;
}

int main()
{
    FILE *f,*g;
    f=fopen("sortaret.in","rt");
    g=fopen("sortaret.out","wt");

    int i,a,b;

    fscanf(f,"%d%d",&n,&m);
    for(i=1;i<=m;i++)
    {
        fscanf(f,"%d%d",&a,&b);
        v[a].push_back(b);
        gr[b]++;
    }
    fclose(f);

    for(i=1;i<=n;i++) if(gr[i]==0 && viz[i]==0) DFS(i);
    for(i=n;i>=1;i--) fprintf(g,"%d ",postordine[i]);
    fprintf(g,"\n");

    fclose(g);
    return 0;
}