Cod sursa(job #1096687)

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

vector<int> Edge[MAX], Path, BigPath;
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]);
    }
    Path.push_back(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])
    {
        Path.resize(0);
        DFS(i);
        reverse(Path.begin(), Path.end());
        BigPath.insert(BigPath.end(), Path.begin(), Path.end());
    }
    for (int i = BigPath.size() - 1; i >= 0; i--)
        printf("%d ", BigPath[i]);
}