Cod sursa(job #1686144)

Utilizator MihaiEMihaiE MihaiE Data 12 aprilie 2016 08:49:15
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.65 kb
#include <stdio.h>
#include <algorithm>
#define nmax 50010

using namespace std;

int n,m,x,y;
bool fr[nmax];
vector <int> g[nmax],sol;

void dfs(int nod)
{
    fr[nod]=true;

    for (int i=0;i<(int)g[nod].size();i++)
        if (!fr[g[nod][i]]) dfs(g[nod][i]);

    sol.push_back(nod);
}

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

    scanf("%d %d",&n,&m);

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

    for (int i=n;i>=1;i--)
        if (!fr[i]) dfs(i);

    for (int i=sol.size()-1;i>=0;i--) printf("%d ",sol[i]);

    return 0;
}