Cod sursa(job #2427370)

Utilizator gabrielsavuSavu Liviu Gabriel gabrielsavu Data 31 mai 2019 17:32:09
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.77 kb
#include <iostream>
#include <fstream>
#include <list>
#include <queue>
#include <bits/stdc++.h>
#include <limits>

std::ifstream sortin("sortaret.in");
std::ofstream sortout("sortaret.out");

using namespace std;

class Link {
private:
    unsigned from;
    unsigned to;
public:
    Link(unsigned from, unsigned to): from(from), to(to) {}
    unsigned getTo() {
        return this->to;
    }

};


class Graph {
private:
    unsigned V;
    std::list<Link> *adj;

public:
    Graph(unsigned V): V(V) {
        adj = new std::list<Link>[V + 1];
    }

    void addEdge(unsigned from, unsigned to) {
        Link first_link(from, to);
        adj[from].push_back(first_link);
    }

    void topologicalSort() {
        std::vector<unsigned> in_degree(V + 1, 0);

        for(unsigned i = 1; i <= this->V; i ++) {
            for(auto u : adj[i]) {
                in_degree[u.getTo()] ++;
            }
        }

        std::queue<unsigned> q;
        for(unsigned i = 1; i <= this->V; i ++) {
            if (in_degree[i] == 0) {
                q.push(i);
            }
        }
        unsigned cnt = 0;

        std::vector<unsigned> top_order;
        while(!q.empty()) {
            unsigned u = q.front();
            q.pop();
            top_order.push_back(u);
            for(auto it : adj[u])
                if (--in_degree[it.getTo()] == 0)
                    q.push(it.getTo());

            cnt ++;
        }
        if (cnt != V) {
            //ciclu
            return;
        }
        for (auto i : top_order)
            sortout << i << " ";
    }

};


int main() {
    int long n, m, a, b;
    sortin >> n >> m;
    auto G = new Graph(n);
    for (unsigned i = 0; i < m; i ++) {
        sortin >> a >> b;
        G->addEdge(a, b);
    }
    G->topologicalSort();

    return 0;
}