Cod sursa(job #2233202)

Utilizator Andrei0872Gatej Andrei Andrei0872 Data 22 august 2018 15:56:39
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.61 kb

#include <iostream>
#include <list>
#include <stack>
#include <fstream>
using namespace std;

int V; // Number of vertices
int E; // Number of edges

// First - the vertex
// Second - the edge length
list<int> *adj; // Adjacency list

void addEdge(int v, int w) {
    adj[v-1].push_back(w-1);
}

void getInput() {

    ifstream f("sortaret.in");

    f >> V >> E;
    adj = new list<int>[V];

    int v,w;
    for(int i = 0; i < E; i++) {
        f >> v >> w;
        addEdge(v,w);
    }

    f.close();
}


void topological_util(int currentNode, bool *visited,stack<int> &st) {

    // Mark the current node as visited
    visited[currentNode]  = true;

    // Adjacent vertices for the current node
    
    // c++11
    // for(auto adjNode:adj[currentNode]) {}
    list<int>::iterator adjNode;
    for(adjNode = adj[currentNode].begin();adjNode != adj[currentNode].end();adjNode++) {
        if(!visited[*adjNode]) {
            topological_util(*adjNode,visited,st);
        }
    }
    // After all its adjacent nodes are added into the stack, add the current node into the stack
    st.push(currentNode);
}

void topological_sort() {

    bool *visited = new bool[V];
    for(int i =0 ; i < V;i++)
        visited[i] = false;

    stack<int> st;

    for(int node = 0; node < V; node++)
        if(!visited[node])
            topological_util(node,visited,st);


    ofstream g("sortaret.out");
    // Print in topological order
    while(!st.empty()) {
        int node = st.top();
        st.pop();
        g << node + 1 << " ";
    }

    g.close();
    delete [] visited;
}

int main () {

getInput();
topological_sort();

return 0;
}