Cod sursa(job #1453731)

Utilizator zsomkoKoman Zsombor zsomko Data 24 iunie 2015 15:04:34
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.21 kb
#include <fstream>
#include <vector>
#include <list>
using namespace std;

vector<list<int> > readit(int &n, int &m, ifstream &in)
{
    int a, b;
    vector<list<int> > w;
    for(int i=0; i<n; i++)
        w.push_back(list<int>());
    for(int i=0; i<m; i++)
    {
        in >> a >> b;
        --a;--b;
        w[a].push_front(b);
    }
    return w;
}

//not prepared to detect non-dag graphs

void sortaret(vector<bool> &v, int &actual, vector<list<int> > &w, list<int> &sorted)
{
    v[actual] = false;
    if(w[actual].size())
    {
        for(list<int>::iterator it = w[actual].begin(); it!=w[actual].end(); ++it)
            if(v[*it])
                sortaret(v, *it, w, sorted);    
    }
    sorted.push_front(actual);
}

int main()
{
    int n, m;
    ifstream in("sortaret.in");
    ofstream out("sortaret.out");
    in >> n >> m;
    vector<list<int> > w = readit(n, m, in);
    vector<bool> v(n);
    for(int i=0; i<n; i++)
        v[i] = true;
    list<int> sorted;
    for(int i=0; i<n; i++)
        if(v[i])
        {
            sortaret(v, i, w, sorted); 
        }
    for(list<int>::iterator it = sorted.begin(); it!=sorted.end(); ++it)
        out << *it+1 << " ";
    in.close();
    out.close();
    return 0;
}