Cod sursa(job #1970482)

Utilizator AurelGabrielAurel Gabriel AurelGabriel Data 19 aprilie 2017 13:17:55
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.26 kb
#include <fstream>
#include <vector>
#include <stack>

using namespace std;

struct graph{
    vector<long int>* adj;
    int s;

    graph(const long int& sz)
    {
        s = sz;
        adj = new vector<long int>[s];
    }

    inline long int size() const
    {
        return s;
    }

    void insert_edge(const long int& u, const long int& v)
    {
        adj[u].push_back(v);
    }
};


stack<long int> sol;
bool b[50000];
void top_sort_util(graph& g, long int node)
{
    b[node] = true;
    for(unsigned long int i = 0; i < g.adj[node].size(); i++)
        if(!b[g.adj[node][i]])
            top_sort_util(g,g.adj[node][i]);
    sol.push(node);
}

void top_sort(graph& g)
{
    for(long int i = 0; i < g.size(); i++)
        if(!b[i])
            top_sort_util(g,i);
}

long int m, n;

int main()
{
    ios_base::sync_with_stdio(false);

    ifstream f("sortaret.in");
    ofstream g("sortaret.out");

    f >> n >> m;
    graph gr(n);

    for(long int i = 0; i < m; i++)
    {
        long int u, v;
        f >> u >> v;
        u--;v--;
        gr.insert_edge(u,v);
    }

    top_sort(gr);
    while(!sol.empty())
    {
        g << sol.top()+1 << ' ';
        sol.pop();
    }

    return 0;
}