Cod sursa(job #2790885)

Utilizator serafimalex2001Serafim Alex serafimalex2001 Data 29 octombrie 2021 18:39:52
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 3.01 kb
#include <iostream>
#include <vector>
#include <queue>
#include <stack>
#include <fstream>

using namespace std;

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

class Graph {
    std::vector<std::vector<int>> Ad;
    int nodes; // no of nodes
    int edges; // no of edges
    int directed; // 1 for directed
public:
    Graph(const std::vector<std::pair<int,int>> &ad, int nodes, int edges,int directed);
    int getComponents();
    void pathTo(int node);
    std::stack<int> topSort();

private:
    void DFS(int node, std::vector<int> &vis);
    void BFS(int node, std::vector<int> &vis);
    void topSortDFS(int node, std::vector<int> &vis, std::stack<int> &s);
};

Graph::Graph(const std::vector<std::pair<int,int>> &ad, int nodes, int edges, int directed) : nodes(nodes), edges(edges), directed(directed) {
    Ad.resize(nodes+1);
    for(int i = 0; i<edges; ++i){
        Ad[ad[i].first].push_back(ad[i].second);
        if(directed == 0)
            Ad[ad[i].second].push_back(ad[i].first);
    }
}

void Graph::DFS(int node, std::vector<int> &vis){
    vis[node] = 1;
    for(int i = 0; i<Ad[node].size(); ++i)
        if(vis[Ad[node][i]] == 0){
            DFS(Ad[node][i], vis);
        }
}

int Graph::getComponents() {
    std::vector<int> vis;
    int ct = 0;
    vis.resize(nodes);
    std::fill(vis.begin(), vis.end(), 0);
    for(int i = 1;i <= nodes; ++i)
        if(vis[i] == 0){
            DFS(i, vis);
            ct++;
        }
    return ct;
}

void Graph::BFS(int node, std::vector<int> &vis){
    int parent, distance;
    std::queue<int> Q;
    Q.push(node);
    vis[node] = 0;
    while(!Q.empty()){
        parent = Q.front();
        Q.pop();
        for(int i = 0; i<Ad[parent].size(); ++i)
            if(vis[Ad[parent][i]] == -1){
                Q.push(Ad[parent][i]);
                vis[Ad[parent][i]] = vis[parent] + 1;
            }
    }
}

void Graph::pathTo(int node){
    std::vector<int> vis;
    vis.resize(nodes+1);
    std::fill(vis.begin(), vis.end(), -1);
    vis[node] = 0;
    BFS(node, vis);
    for(int i = 1; i<= nodes; ++i)
        fout << vis[i]<< " ";
}

void Graph::topSortDFS(int node, std::vector<int> &vis, std::stack<int> &s){
    vis[node] = 1;
    for(int i = 0; i<Ad[node].size(); ++i)
        if(vis[Ad[node][i]] == 0)
            topSortDFS(Ad[node][i], vis, s);
    s.push(node);
}

std::stack<int> Graph::topSort(){
    std::vector<int> vis;
    std::stack<int> s;
    vis.resize(nodes+1);
    std::fill(vis.begin(), vis.end(), 0);
    for(int i = 1; i<=nodes; ++i)
        if(!vis[i])
           topSortDFS(i, vis, s);
    return s;
}

int main() {
    std::vector<std::pair<int,int>> Ad;
    std::stack<int> s;
    int n,m,x,y;
    fin >> n >> m;
    for(int i = 0; i<m; ++i){
        fin >> x >> y;
        Ad.push_back({x,y});
    }
    Graph G(Ad,n ,m, 1);
    s = G.topSort();
    while(!s.empty()){
        fout << s.top() << " ";
        s.pop();
    }
    return 0;
}