Cod sursa(job #1066169)

Utilizator dobrebogdanDobre Bogdan Mihai dobrebogdan Data 24 decembrie 2013 09:14:59
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.76 kb
#include <stdio.h>
#include <cstring>
#include <vector>
using namespace std;
vector <int> g[50005];
int v[50005],l;
bool f[50005];
void dfs(int nod)
{
    int i;
   for(i=g[nod].size()-1;i>=0;i--)
        if(f[g[nod][i]]==0)
        {
            f[g[nod][i]]=1;
            dfs(g[nod][i]);
        }
l++;
    v[l]=nod;
}

int main()
{
    freopen("sortaret.in","r",stdin);
    freopen("sortaret.out","w",stdout);
    int n,m,i,x,y;
    scanf("%d%d",&n,&m);
    for(i=1;i<=m;i++)
    {
        scanf("%d%d",&x,&y);
        g[x].push_back(y);
    }
l=0;
    for(i=1;i<=n;++i)
        if(f[i]==0)
        {
            f[i]=1;
            dfs(i);
        }
    for(i=n;i>0;i--)
        printf("%d ",v[i]);
    printf("\n");

    return 0;
}