Cod sursa(job #2800828)

Utilizator SG2021StancuGeorge SG2021 Data 14 noiembrie 2021 02:09:57
Problema Sortare topologica Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.03 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[101];
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[101];



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 ;
    st.push_back(v);  
    for(auto j = Graph[v] ; !j->empty();j->forward()){
        if(!viz[j->getvalue()]){
            topologicalSort(j->getvalue());
        }

    }  

}

int main()
{
   input();
   for(int i = 1 ; i <= n ; i++ ){
       cout << i << ": "; 
       Graph[i]->output();
       cout << endl ;
   }cout << endl ;
   for(int i = 1 ; i <= n ; i ++ ){
       viz[i] = false;
   }
   for(int i = 1 ; i <= n ; i++ ){
       if(viz[i] == false) topologicalSort(i);

   }
   for(auto val : st){
       g << val << " " ;
   }


}