Cod sursa(job #1115825)

Utilizator avram_florinavram florin constantin avram_florin Data 22 februarie 2014 02:31:38
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.04 kb
// Se da un graf orientat aciclic G=(V,E). Se doreste o sortare topologica a
// varfurilor grafului. O sortare topologica este o operatie de ordonare astfel
// incat, daca exista un arc (i,j) atunci i apare inaintea lui j in aceasta
// sortare.
// Complexitate dorita: O(|V|+|E|)
// Idee: Se face o parcurgere in adancime a grafului(DFS), iar atunci cand nodul
// vizitat nu mai are vecini, atunci el este adaugat in stiva. La final se vor
// scoate nodurile din stiva :D

#include <iostream>
#include <fstream>
#include <vector>
#include <stack>

const char InFile[] = "sortaret.in";
const char OutFile[] = "sortaret.out";

class TopSort{
    int V,E;

    std::vector< std::vector<int> > graph;
    std::stack<int> stack;
    std::vector<bool> visited;

    public:
        TopSort(int V, int E) : V(V) , E(E){
            graph.resize(V+1);
            visited.resize(V+1);
        }

        void addEdge(int x, int y){
            graph[x].push_back(y);
        }
        
        void DFS(int nod){
            visited[nod] = true;

            std::vector<int>::iterator it;
            for( it = graph[nod].begin() ; it < graph[nod].end() ; it++ ){
                if( !visited[*it] )
                    DFS(*it);
            }
            stack.push(nod);
        }

        void solve(){
            for( int i=1 ; i<=V ; i++ )
                if( !visited[i] )
                    DFS(i);
        }

        friend std::ostream& operator<< (std::ostream& out, TopSort& G);
};

std::ostream& operator<< (std::ostream& out, TopSort& G)
{
    while( !G.stack.empty() ){
        out << G.stack.top() << ' ';
        G.stack.pop();
    }
    out << '\n';
    return out;
}

TopSort readData(std::istream& in)
{
    int V, E, x, y;

    in >> V >> E;
    TopSort G(V,E);

    for( int i=0 ; i<E ; i++ ){
        in >> x >> y;
        G.addEdge(x, y);
    }
    return G;
}

int main(void)
{
    std::ifstream in(InFile);
    std::ofstream out(OutFile);

    TopSort topSort = readData(in);
    topSort.solve();

    out << topSort;

    in.close();
    out.close();
    return 0;
}