Cod sursa(job #2796548)

Utilizator Andrei_SturzuAndrei Sturzu Andrei_Sturzu Data 8 noiembrie 2021 14:04:03
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 3.87 kb
#include<iostream>
#include<queue>
#include<vector>
#include<fstream>
#include<queue>
#include<stack>

using namespace std;

class Graph{
    private:
        int numberOfNodes = 0;
        int numberOfEdges = 0;
        vector<int> nodes;
        vector<vector<int>> neighbours;


    public:
        Graph(int n);
        Graph() {};
        int getNumberOfNodes() {return this->numberOfNodes;};
        void addDirectedEdge(int a, int b);
        void addUndirectedEdge(int a, int b);
        void bfs(int node);
        vector<int> bfs_cost(int node);
        void dfs(int node, vector<int> &visited);
        int NumberOfConnectedComponets();
        void topoSortDFS(int node, vector<int> &visited, stack<int> & s);
        vector<int> topoSort();
};

Graph::Graph(int n){
    this->numberOfNodes = n;
    for(int i = 0; i <=n; i++)
        this->neighbours.push_back(vector<int>());
}

void Graph::addUndirectedEdge(int a, int b){
    this->neighbours[a].push_back(b);
    this->neighbours[b].push_back(a);
    this->numberOfEdges++;
}

void Graph::addDirectedEdge(int a, int b){
    this->neighbours[a].push_back(b);
    this->numberOfEdges++;
}

void Graph::bfs(int node){
    vector<int> visited(this->getNumberOfNodes() + 1);
    queue<int> q;

    q.push(node);
    visited[node] = 1;

    while(!q.empty()) {
        int currentNode = q.front();
        cout<<currentNode<<" ";
        q.pop();
        for(int i: this->neighbours[currentNode]) {
            if(!visited[i]) {
                q.push(i);
                visited[i] = 1;
            }
        }
    }
    cout<<"\n";
}

vector<int> Graph::bfs_cost(int node){
    vector<int> visited(this->getNumberOfNodes() + 1);
    queue<int> q;
    vector<int> cost(this->getNumberOfNodes() + 1);

    q.push(node);
    visited[node] = 1;

    while(!q.empty()) {
        int currentNode = q.front();
        q.pop();
        for(int i: this->neighbours[currentNode]) {
            if(!visited[i]) {
                q.push(i);
                cost[i] = cost[currentNode] + 1;
                visited[i] = 1;
            }
        }
    }

    for(int i = 1; i <= this->getNumberOfNodes(); i++){
        if(!visited[i])
            cost[i] = -1;
    }

    return cost;
}

void Graph::dfs(int node, vector<int> &visited) {
    visited[node] = 1;
    for(int i: this->neighbours[node])
        if(!visited[i])
            this->dfs(i, visited);

}

int Graph::NumberOfConnectedComponets() {
    vector<int> visited(this->getNumberOfNodes() + 1);
    int countConnected = 0;

    for(int i = 1; i <= this->getNumberOfNodes(); i++) {
        if(visited[i] == 0) {
            this->dfs(i, visited);
            countConnected++;
        }
    }

    return countConnected;
}

void Graph::topoSortDFS(int v, vector<int> &visited, stack<int>& s) {
    visited[v] = 1;

    for (auto neighbour : this->neighbours[v])
        if (!visited[neighbour])
            this->topoSortDFS(neighbour, visited, s);
    s.push(v);
}

vector<int> Graph::topoSort()
{
    stack<int> Stack;
    vector<int>tOrder;

    vector<int> visited(this->getNumberOfNodes() + 1);

    for (int i = 1; i <= this->getNumberOfNodes(); i++)
        if (visited[i] == false)
            this->topoSortDFS(i, visited, Stack);

    // Print contents of stack
    while (!Stack.empty()) {
        tOrder.push_back(Stack.top());
        Stack.pop();
    }

    return tOrder;
}

int main() {
    int n, m, startNode;

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

    fin >> n >> m;

    Graph graph = Graph(n);

    for(int i = 1; i <= m; i ++)
    {
        int a, b;
        fin >> a >> b;
        graph.addDirectedEdge(a,b);
    }

    vector<int> result = graph.topoSort();
    for(int node: result)
        fout<<node<<' ';

    return 0;
}