Cod sursa(job #2556851)

Utilizator ZahaZaharie Stefan Zaha Data 25 februarie 2020 11:23:02
Problema Sortare topologica Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.13 kb
#include <fstream>
#include <vector>
#include <queue>
using namespace std;

ifstream fin("sortaret.in");
ofstream fout("sortaret.out");
vector <int> muchii[100005];
bool vizitat[100005];
bool are_tata[100005];
bool exista_nod[100005];

void find(int nod) {
    for (unsigned int i = 0; i < muchii[nod].size(); ++i) {
        int vecin = muchii[nod][i];
        if (vizitat[vecin])
            continue;

        fout << vecin << " ";
        if (!muchii[vecin].empty())
            find(vecin);

        vizitat[vecin] = true;
    }
}

int main() {
    int n, m;
    fin >> n >> m;
    queue <int> tati;
    
    for (int i = 1; i <= m; ++i) {
        int x, y;
        fin >> x >> y;
        muchii[x].push_back(y);
        are_tata[y] = true;
        tati.push(x);
        exista_nod[x] = true;
        exista_nod[y] = true;
    }

    for (int i = 1; i <= n; ++i)
        if (!exista_nod[i])
            fout << i << " ";

    while (!tati.empty()) { //find root
        if (!are_tata[tati.front()]) {
            fout << tati.front() << " ";
            find(tati.front());
            break;
        }
        tati.pop();
    }
    
    return 0;
}