Cod sursa(job #2432674)

Utilizator alex.livadaruLivadaru Alexandru alex.livadaru Data 24 iunie 2019 18:23:48
Problema Sortare topologica Scor 90
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.51 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <list>
#include <iterator>
#define NMAX 50000
using namespace std;

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

class Graph {
    public:
        vector<int> adjList[NMAX];
        vector<bool> visited;
        vector<int> tdesc;
        vector<int> order;
        int contor = 0;
        int nodes;

        Graph(int n) {
            visited.resize(n + 1, 0);
            tdesc.resize(n + 1, 0);
            nodes = n;
        }

        ~Graph() {

        }

        void addEdge(int x, int y) {
            adjList[x].push_back(y);
        }

        void DFS(int nod) {
            for (int i = 0; i < adjList[nod].size(); ++i) {
                if (visited[adjList[nod][i]] == 0) {
                    visited[adjList[nod][i]] = 1;
                    ++contor;
                    DFS(adjList[nod][i]);
                }
            }
            tdesc[nod] = contor;
            order.push_back(nod);

        }

        void Top_Sort() {
            for (int i = 1; i <= nodes; ++i) {
                if (visited[i] == 0) {
                    visited[i] = 1;
                    DFS(i);
                }
            }
            for (int i = order.size() - 1; i >= 0; --i) {
                fout << order[i] << " ";
            }
        }



};

int main() {
    int n, m, x, y;
    fin >> n >> m;
    Graph graf(n);
    for (int i = 0; i < m; ++i) {
        fin >> x >> y;
        graf.addEdge(x, y);
    }
    graf.Top_Sort();

    return 0;
}