Cod sursa(job #1970466)

Utilizator AurelGabrielAurel Gabriel AurelGabriel Data 19 aprilie 2017 13:06:10
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.19 kb
#include <fstream>
#include <vector>

using namespace std;

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

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

    long int size() const
    {
        return s;
    }

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


vector<long int> sol;
bool b[50000];
void top_sort_util(graph& g, long int node)
{
    b[node] = true;
    sol.push_back(node);
    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]);
}

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()
{
    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);
    for(unsigned long int i = 0; i < sol.size(); i++)
        g << sol[i]+1 << ' ';

    return 0;
}