Cod sursa(job #2822400)

Utilizator catarau.bianca.Bianca Catarau catarau.bianca. Data 23 decembrie 2021 22:29:45
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.17 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <algorithm>
#include <bits/stdc++.h>

using namespace std;

ifstream f("sortaret.in");
ofstream g("sortaret.out");


class graf{
   int n, m;
   stack <int> S;
   bool vizitate[100001];
   vector <int> muchii[100001];
   void st(int s);
public:
    graf(int n, int m);
    void citire_orientat(int m);
    void sortare_topologica();
};
graf::graf(int n,int m)
{
    this->n = n;
    this->m = m;
}
void graf::citire_orientat(int m)
{
    int nod1, nod2;
    for (int i = 0; i <= m; i++)
    {
        f >> nod1 >> nod2;
        muchii[nod1].push_back(nod2);
    }
}
void graf :: st(int s)
{
    vizitate[s] = true;
    for(int i : muchii[s])
        if(!vizitate[i])
            st(i);
    S.push(s);
}

void graf ::sortare_topologica()
{

    for(int i = 1; i <= n; ++i)
        if(!vizitate[i])
            st(i);
    while(!S.empty())
    {g << S.top() << " ";
    S.pop();}//afisam stiva cu rezultatul final
}
int main()
{
    int n, m;
    f >>n>>m;
    graf G(n,m);
    G.citire_orientat(m);
    G.sortare_topologica();
    return 0;
}