Cod sursa(job #2534601)

Utilizator teomdn001Moldovan Teodor teomdn001 Data 30 ianuarie 2020 19:35:49
Problema Sortare topologica Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.08 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

ifstream fin("sortaret.in");
ofstream fout("sortaret.out");

struct Nod{
    int nod;
    int cost;
};

int n, m;
Nod vizitat[50005];
vector <int> G[50005];
queue <int> Q;

void Dfs(int nod, int pas);
bool maiMare(const Nod &x, const Nod &y)
{
    return (x.cost <= y.cost);
}

int main()
{
    fin >> n >> m;
    int x, y;
    for (int i = 1; i <= m; ++i)
    {
        fin >> x >> y;
        G[x].push_back(y);
    }

    for (int i = 1; i <= n; ++i)
    {
        if (!vizitat[i].cost)
        {
            Dfs(i, 1);
        }
    }


    std::sort(vizitat + 1, vizitat + n + 1, maiMare);
    for (int i = 1; i <= n; ++i)
        fout << vizitat[i].nod << ' ';

}
void Dfs(int nod, int pas)
{
    vizitat[nod].nod = nod;
    vizitat[nod].cost = pas;
    Q.push(nod);
    for (int i = 0; i < G[nod].size(); ++i)
    {
        int nou = G[nod][i];
        if (!vizitat[nou].cost)
            Dfs(nou, pas + 1);
    }
}