Cod sursa(job #2905293)

Utilizator VladPislaruPislaru Vlad Rares VladPislaru Data 20 mai 2022 18:08:57
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.76 kb
#include <bits/stdc++.h>

using namespace std;
const int dim = 50005;

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

class Graph
{
private:
    int node_count, edge_count;
    vector <int> adj[dim];
public:
    Graph ()
    {
        node_count = 0;
        edge_count = 0;
    }
    Graph (int nodes, int edges)
    {
        node_count = nodes;
        edge_count = edges;
    }
    void Make_Graph (int nodes, int edges)
    {
        node_count = nodes;
        edge_count = edges;
    }
    void Add_edge (int node1, int node2)
    {
        adj[node1].push_back(node2);
    }
    int NrNoduri ()
    {
        return node_count;
    }
    void Afis_Graph ()
    {
        for (int i = 1; i <= node_count; i++, cout << "\n")
        {
            cout << i << ": ";
            for (int j : adj[i])
                cout << j << " ";
        }

    }
    void DFS_SortTop (int node, vector <int> &viz, stack <int> &st)
    {
        viz[node] = 1;
        for (int i : adj[node])
            if (!viz[i])
                DFS_SortTop(i, viz, st);
        st.push(node);
    }
    stack <int> SortTop (vector <int> &viz, stack <int> &st)
    {
        for (int i = 1; i <= node_count; i++)
            if (!viz[i])
            {
                DFS_SortTop(i, viz, st);
            }

        return st;
    }
};

vector <int> viz(dim);
stack <int> st;
Graph G;

int main()
{
    int n , m;
    fin >> n >> m;
    G.Make_Graph(n , m);
    for (int i = 1;  i<= m; i++)
    {
        int x, y;
        fin >> x >> y;
        G.Add_edge(x, y);
    }
    stack <int> sol = G.SortTop(viz, st);
    while (!sol.empty())
    {
        fout << sol.top() << " ";
        sol.pop();
    }
    return 0;
}