Cod sursa(job #2334636)

Utilizator AndreiBadescuBadescu Andrei-Octavian AndreiBadescu Data 2 februarie 2019 19:35:55
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.21 kb
#include <fstream>
#include <vector>
#include <stack>

using namespace std;
typedef unsigned int uint;

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

class Graph
{
    uint V;
    vector<vector<uint>> adj;
    void DFS(uint n, vector<bool> &v, stack<uint> &s);
public:
    Graph(const uint V);
    void Add_edge(uint x, uint y);
    void TopologicalSort();
};

Graph::Graph(const uint V)
{
    this->V = V;
    adj.assign(V + 1, vector<uint>());
}

void Graph::Add_edge(uint x, uint y)
{
    adj[x].emplace_back(y);
}

void Graph::DFS(uint n, vector<bool> &v, stack<uint> &s)
{
    v[n] = true;
    for (auto &i : adj[n])
        if (!v[i])
            DFS(i,v,s);

    s.push(n);
}

void Graph::TopologicalSort()
{
    vector<bool> v(V + 1, false);
    stack<uint> sol;

    for (uint i = 1; i <= V; ++i)
    {
        if (!v[i])
            DFS(i,v,sol);
    }

    while (!sol.empty())
    {
        fout << sol.top() << ' ';
        sol.pop();
    }
}

int main()
{
    uint n,m;
    fin >> n >> m;

    Graph G(n);

    for (uint x,y,i = 0; i < m; ++i)
    {
        fin >> x >> y;
        G.Add_edge(x,y);
    }

    G.TopologicalSort();
}