Cod sursa(job #928111)

Utilizator andrettiAndretti Naiden andretti Data 26 martie 2013 11:30:49
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.78 kb
#include<stdio.h>
#include<vector>
#define maxn 50005
using namespace std;

int n,m,u;
int v[maxn],c[maxn];
vector <int> l[maxn];

void cit()
{
    int i;
    int x,y;

    scanf("%d%d",&n,&m);
    for(i=1;i<=m;i++)
    {
        scanf("%d%d",&x,&y);
        l[x].push_back(y);
    }
}

void df(int k)
{
    v[k]=1;
    for(unsigned int i=0;i<l[k].size();i++)
        if(v[l[k][i]]==0)
            df(l[k][i]);
    c[++u]=k;
}

void afis()
{
   int i;
   for(i=n;i>=1;i--)
    printf("%d ",c[i]);
}

int main()
{
    freopen("sortaret.in","r",stdin);
    freopen("sortaret.out","w",stdout);

    cit();
    int i;
    for(i=1;i<=n;i++)
        if(v[i]==0)
         df(i);
    afis();

    fclose(stdin);
    fclose(stdout);
    return 0;
}