Cod sursa(job #2715044)

Utilizator iuliangal186Gal Iulian iuliangal186 Data 2 martie 2021 20:58:53
Problema Sortare topologica Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.52 kb
#include <iostream>
#include <list>
#include <stack>
#include <fstream>

using namespace std;

ifstream fin("sortaret.in");
ofstream fout("sortaret.out");

class Graph{
    int v;

    list<int>* adj;

    void sorttopo(int v, bool visited[], stack<int>& stack);

public:
    //constructor
    Graph(int v);
    
    //to add edge in graph
    void addEdge(int v, int w);

    //to print topological sort
    void topologicalSort();
};

Graph :: Graph(int v)
{
    this -> v = v;
    adj = new list<int>[v];
}

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

//topsort
void Graph :: sorttopo(int v, bool visited[], stack<int>& stack)
{
    visited[v] = true;

    list<int> :: iterator i;
    for(i = adj[v].begin(); i != adj[v].end(); i++)
    {
        if(!visited[*i])
            sorttopo(*i, visited, stack);
    }
    stack.push(v);
}

void Graph :: topologicalSort()
{
    stack<int> stack;
    bool* visited = new bool[v];
    for(int i = 0; i < v; i++)
    {
        visited[i] = false;
    }
    for(int i = 0; i < v; i++)
    {
        if(visited[i] == false)
        {
            sorttopo(i, visited, stack);
        }

    }
    while(stack.empty() == false)
    {
        fout << stack.top() << " ";
        stack.pop();
    }
}
int main()
{
    int n, m, x, y;
    fin >> n >> m;
    Graph g(n);
    for(int i = 1; i <= m; i++)
    {
        fin >> x >> y;
        g.addEdge(x, y);
    }
    g.topologicalSort();
    return 0;
}