Cod sursa(job #1089955)

Utilizator kiralalaChitoraga Dumitru kiralala Data 22 ianuarie 2014 08:44:48
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.84 kb
#include <fstream>
#include <vector>
#include <stack>
#define NMAX 50005

using namespace std;

FILE* f=freopen("sortaret.in","r",stdin);
FILE* o=freopen("sortaret.out","w",stdout);

int n,m;
vector<int> graph[NMAX];
int vis[NMAX];
stack<int> output;

void PostOrder(int x)
{
    vis[x]=1;
    for(int i=0;i<graph[x].size();++i)
        if(!vis[graph[x][i]]) {
            PostOrder(graph[x][i]);
        }
    output.push(x);
}

void Tsort()
{
    for(int i=1;i<=n;++i)
        if(!vis[i])
            PostOrder(i);
}

int main()
{
    scanf("%d%d",&n,&m);

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

    Tsort();

    while(!output.empty())
    {
        int x=output.top();
        output.pop();
        printf("%d ",x);
    }

    return 0;
}