Cod sursa(job #2048543)

Utilizator SilviuIIon Silviu SilviuI Data 26 octombrie 2017 11:06:20
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.74 kb
#include <stdio.h>
#include <vector>
#define nmax 50010

using namespace std;

int n, m;
bool fr[nmax];

vector <int> v[nmax];
vector <int> ans;

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

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

    ans.push_back(node);
}

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

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

    for (int i = 1; i <= m; i++) {

        int x, y;

        scanf("%d %d", &x, &y);

        v[x].push_back(y);
    }

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

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

    return 0;
}