Pagini recente » Cod sursa (job #1729957) | Cod sursa (job #793644) | Cod sursa (job #1135639) | Cod sursa (job #1609467) | Cod sursa (job #1115825)
// 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;
}