Cod sursa(job #2178205)

Utilizator silvereaLKovacs Istvan silvereaL Data 19 martie 2018 11:30:05
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.1 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>

using namespace std;

const int M = 50001;

ifstream fcin("sortaret.in");
ofstream fcout("sortaret.out");

vector<int> V[M], T;
stack<int> s;
int n, m, x, y, k[M];
bool visited[M];

int main()
{
    fcin >> n >> m;
    for (int i = 0; i < m; ++i)
    {
        fcin >> x >> y;
        V[x].push_back(y);
    }

    k[1] = 0;
    visited[1] = true;
    s.push(1);

    while (!s.empty())
    {
        int sn = s.top();
        s.pop();
        ++x;
        for (int i = 0; i < V[sn].size(); ++i)
            if (!visited[V[sn][i]])
            {
                visited[V[sn][i]] = true;
                s.push(V[sn][i]);
                k[V[sn][i]] = k[sn] + 1;
            }
    }

    x = k[1];
    for (int i = 2; i <= n; ++i)
        if (k[i] > x)
            x = k[i];

    T.push_back(1);
    for (int i = 0; i <= x; ++i)
        for (int j = 2; j <= n; ++j)
            if (k[j] == i)
                T.push_back(j);

    for (int i = 0; i < T.size(); ++i)
        fcout << T[i] << ' ';
}