Cod sursa(job #1744893)

Utilizator daymon_cDumitru Chitoraga daymon_c Data 20 august 2016 17:56:36
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.73 kb
#include <stdio.h>
#include <vector>

using namespace std;

vector<int> v[50005];
bool used[50005];
int s[50005], ind;

void bfs(int x)
{
    for(int i = 0; i < v[x].size(); ++i)
    {
        if(!used[v[x][i]])
        {
            bfs(v[x][i]);
        }
    }
    used[x] = 1;
    s[ind++] = x;
}

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

    int n, m;

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

    for(int i=0; i<m; ++i)
    {
        int a, b;
        scanf("%d%d", &a, &b);
        v[a].push_back(b);
    }

    for(int i=1; i<=n; ++i)
    {
        if (!used[i])
        {
            bfs(i);
        }
    }

    for(ind = ind - 1; ind>=0; --ind)
        printf("%d ", s[ind]);

    return 0;
}