Cod sursa(job #1096699)

Utilizator dropsdrop source drops Data 2 februarie 2014 15:24:28
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.82 kb
/* Sortare topologica a varfurilor unui graf */
#include <cstdio>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;
#define MAX 50001

vector<int> Edge[MAX];
stack<int> St;
bool Was[MAX];
int N, M;

void DFS(int X)
{
    Was[X] = 1;
    for (int i = 0; i < Edge[X].size(); i++)
    if (!Was[Edge[X][i]])
    {
        DFS(Edge[X][i]);
    }
    St.push(X);
}

int main()
{
    int A, B;
    freopen("sortaret.in","r",stdin);
    freopen("sortaret.out","w",stdout);
    scanf("%d %d", &N, &M);
    for (int i = 0; i < M; i++)
    {
        scanf("%d %d", &A, &B);
        Edge[A].push_back(B);
    }
    for (int i = 1; i <= N; i++)
    if (!Was[i])
    {
        DFS(i);
    }
    while (St.size() > 0)
    {
        printf("%d ", St.top());
        St.pop();
    }
}