Cod sursa(job #2834236)

Utilizator rusenmihai101@gmail.comMihai Rusen [email protected] Data 16 ianuarie 2022 18:01:37
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.03 kb
#include <fstream>
#include <vector>
#include <cstring>
using namespace std;

class InParser{
    private:
        vector < char > str;
        int position;
        ifstream fin;

        char GetChar(){
            if(position == (int) str.size()){
                fin.read(str.data(), position);
                position = 0;
            }
            return str[position++];
        }

        template < class DataType >
        DataType GetInteger(){
            char ch = GetChar();
            while( ! isdigit(ch) && ch != '-')
                ch = GetChar();
            int sgn = 1;
            if(ch == '-'){
                sgn = -1;
                ch = GetChar();
            }
            DataType number = 0;
            while(isdigit(ch)){
                number = number * 10 + ch - 48;
                ch = GetChar();
            }
            return sgn * number;
        }
    public:
        InParser(const string name): position(1e4), str(1e4), fin(name){}
        ~InParser(){
            fin.close();
        }
        template < class DataType >
        friend InParser& operator >> (InParser& in, DataType& number){
            number = in.GetInteger< DataType >();
            return in;
        }
};

int_fast32_t Nodes, Edges, BeenThere[50001], InsideGrade[50001];
vector < int_fast32_t > Edge[50001], ans;

inline static void DFS(int_fast32_t node){
    BeenThere[node] = true;
    for(auto Neighbour: Edge[node])
        if( ! BeenThere[Neighbour])
            DFS(Neighbour);
    ans.push_back(node);
}

int main(){

    string name("sortaret");
    InParser fin(name + ".in");
    ofstream fout(name + ".out");
    fin >> Nodes >> Edges;
    register int i;
    int_fast32_t node1, node2;
    for(i = 1; i <= Edges; ++i){
        fin >> node1 >> node2;
        Edge[node1].push_back(node2);
        ++InsideGrade[node2];
    }
    for(i = 1; i <= Nodes; ++i)
        if( ! InsideGrade[i])
            DFS(i);
    for(vector < int_fast32_t > :: reverse_iterator it = ans.rbegin(); it != ans.rend(); ++it)
        fout << *it << ' ';

    return 0;
}