Cod sursa(job #2801088)

Utilizator SG2021StancuGeorge SG2021 Data 14 noiembrie 2021 21:46:17
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.93 kb
#include <iostream> 
#include <fstream>
#include <stack>
#include <vector>
using namespace std;
ifstream f("sortaret.in");
ofstream g("sortaret.out");
vector<int> st; 
int n , m ;
bool viz[50001];
struct Vertex{
    int info;
    Vertex * urm ;
};
struct list{
    Vertex * head;
    void init(){
        head = NULL;
    }
    void add(int x){
        Vertex * x1 = new Vertex;
        x1->urm = NULL;
        x1->info = x ;
        if(head==NULL){
            head = x1;
        }else{
            Vertex * HeadCopy = head;
            while(head->urm!=NULL){
                head = head->urm;
            }
            head->urm = x1;
            head = HeadCopy;
        }
    }
    bool empty(){
        return(head==NULL);
    }
    void output(){
        if(head!=NULL) {
            Vertex * headCopy =  head;
            while(head!=NULL) { 
                cout << head->info << " " ;
                head = head -> urm ;
            }   
            head = headCopy;
        }
    }
    void forward(){
        if(head!=NULL) head = head->urm;
    }
    int getvalue(){
        return head->info;
    }
}*Graph[50001];
 
 
 
void input()
{
    
    f >> n >> m ;
    for(int i = 1 ; i <= n ; i++ ){
        Graph[i] = new list;
        Graph[i]->init();
 
    }
    for(int i = 1 ; i <= m ; i++ ){
        int x , y ;
        f >> x >> y; 
        Graph[x]->add(y);
    }
}
void topologicalSort(int v)
{
    viz[v] = true ; 
    for(auto j = Graph[v] ; !j->empty();j->forward()){
        if(!viz[j->getvalue()]){
            topologicalSort(j->getvalue());
        }
 
    }
    st.push_back(v); 
 
}
 
int main()
{
   input();
   for(int i = 1 ; i <= n ; i ++ ){
       viz[i] = false;
   }
   for(int i = 1 ; i <= n ; i++ ){
       if(viz[i] == false) topologicalSort(i);
 
   }
   for(int i = st.size()-1 ; i >= 0 ; i-- )
   {
       g << st[i] << " ";
   }
 
 
}