Cod sursa(job #2425109)

Utilizator no_name_requiredNo Name Required no_name_required Data 24 mai 2019 12:30:44
Problema Sortare topologica Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.29 kb
#include <bits/stdc++.h>

using namespace std;

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

unordered_set<int> unmarked;

class Graph
{
private:
    int n, m;
    vector<vector<int>>edges;
public:
    Graph(int _n, int _m) : n{_n}, m{_m}{
        edges.resize(_n + 1, vector<int>());
    }
    void addEdge(int x, int y){
        edges[x].push_back(y);
    }

    vector<int> getTopologicSort(int startNode)
    {
        queue<int> q;
        vector<int> answ;
        q.push(startNode);

        while (!q.empty())
        {
            int k = q.front(); q.pop();
            unmarked.erase(unmarked.find(k));
            answ.push_back(k);
            for (int &x : edges[k])
                    q.push(x);
        }
        return answ;
    }
};

int main()
{
    int n, m, x, y, startNode;
    fin >> n >> m;

    Graph g(n, m);

    fin >> x >> y;
    g.addEdge(x, y);
    startNode = x;

    for (int i = 2; i <= m; ++i)
    {
        fin >> x >> y;
        g.addEdge(x, y);
    }

    for(int i = n; i >= 1; i--)
		unmarked.emplace(i);

    while (unmarked.size())
    {
        vector<int> answ = g.getTopologicSort(startNode);
        for_each(answ.begin(), answ.end(), [](int &c) {fout << c << " ";});
    }

    return 0;
}