Cod sursa(job #2921345)

Utilizator CiobaCatalinCioba Catalin CiobaCatalin Data 30 august 2022 13:36:14
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.01 kb
#include <algorithm>
#include <fstream>
#include <iostream>
#include <queue>
#include <vector>

using namespace std;

class Graph
{
public:
    Graph(int vertices)
    {
        adj.resize(vertices + 1);
        this->vertices = vertices;
    }

    void addEdge(int from, int to)
    {
        // cout << "adding " << from << "->" << to << endl;
        auto &adjFrom = adj[from];
        adjFrom.push_back(to);
    }

    vector<int> topSort()
    {
        // cout << "TopSort begin" << endl;
        vector<int> inDegree(vertices + 1, 0);

        for (auto adjIt = adj.begin(); adjIt != adj.end(); adjIt++)
        {
            if (adjIt == adj.begin())
            {
                continue;
            }
            for (auto el : *adjIt)
            {
                inDegree[el]++;
            }
        }

        // for (int i = 0; i <= vertices; i++) {
        //     cout << "inDegree[" << i <
        // }

        queue<int> q;
        for (auto it = inDegree.begin(); it != inDegree.end(); it++)
        {
            if (it == inDegree.begin())
            {
                continue;
            }
            if (*it == 0)
            {
                q.push(it - inDegree.begin());
            }
        }

        vector<int> result;
        while (!q.empty())
        {
            int el = q.front();
            q.pop();
            result.push_back(el);

            for (auto neighbor : adj[el])
            {
                inDegree[neighbor]--;
                if (inDegree[neighbor] == 0)
                {
                    q.push(neighbor);
                }
            }
        }

        return result;
    }

private:
    vector<vector<int>> adj;
    int vertices;
};

int main()
{
    ifstream in("sortaret.in");
    ofstream out("sortaret.out");

    int n, m;
    in >> n >> m;
    Graph g(n);

    int from, to;
    for (int i = 0; i < m; i++)
    {
        in >> from >> to;
        g.addEdge(from, to);
    }

    auto topSort = g.topSort();

    for (auto el : topSort)
    {
        out << el << " ";
    }
}