Cod sursa(job #2025214)

Utilizator circeanubogdanCirceanu Bogdan circeanubogdan Data 22 septembrie 2017 08:05:47
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.87 kb
#include <fstream>
#include <vector>
#define DIM 50002

using namespace std;

ifstream f("sortaret.in");
ofstream g("sortaret.out");

int n, m, x, y, ok, viz[DIM];

vector <int> sol, graf[DIM];

void dfs(int nod)
{
    viz[nod] = 1;
    for(int i = 0; i < graf[nod].size(); ++ i)
        if(viz[graf[nod][i]] == 0)
            dfs(graf[nod][i]);
    sol.push_back(nod);
}

void afis()
{
    for(int i = sol.size() - 1; i >= 0; -- i)
        g<<sol[i]<<" ";
}

int main()
{
    f>>n>>m;
    for(int i = 1; i <= m; ++ i)
    {
        f>>x>>y;
        ok = 1;
        for(int j = 0; j < graf[x].size(); ++ j)
            if(graf[x][j] == y)
                ok = 0;
        if(ok == 1)
            graf[x].push_back(y);
    }
    for(int i = 1; i <= n; ++ i)
    {
        if(viz[i] == 0)
            dfs(i);
    }
    afis();
    return 0;
}