Cod sursa(job #2494481)

Utilizator NMadrianNechiti Mihai Adrian NMadrian Data 17 noiembrie 2019 22:17:27
Problema Sortare topologica Scor 20
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.58 kb
#include <fstream>
//#include <iostream>

std:: ifstream in("sortaret.in");
std:: ofstream out ("sortaret.out");
const int MAX=100005;
struct nod {
int vf ;
nod* urm ;
}*L[MAX],*p,*sf,*manevra;
int N , M , vizitat[MAX];

void citire();
void add(int , int);
void dfs(int);
int main(){
citire();
///7 6 3 4 1 2 5
///initializare solutie
//p->vf = 1,p->urm =nullptr;


for(int i =1 ; i<=N;i++)
{
sf = p;
    if(!vizitat[i]){
           nod *t = new nod ;
           t->vf = i;
           t->urm = p ;
           p=t;
           manevra=p ;
    dfs(i);
    }
}
while(p!=nullptr)
{
    out<<p->vf <<" ";
    p=p->urm;
}

///afisare pt verificare
/*for(int i = 1 ; i <=N ; i++ )
{out << i << " :: ";
    nod *  p = L[i];
    while(p!=nullptr)
 {
out << p->vf<< " ";
p=p->urm;
 }
out << "NULL \n";
}*/
return 0;
}
void citire(){
in >> N >> M ;

for(int i =1;i<=M;i++)
{
   int x , y ;
   in >> x >> y;
   add(x,y);
  }
}

void add(int x,int y){
nod * p = new nod ;
p -> urm = nullptr;
p ->vf = y;

if(L[x]==nullptr)
    L[x]=p;
else{
    bool ok=false;
    nod* t = L[x];
    if(t->vf == y)
        ok=true;
    while(t->urm != nullptr)
        {
            t = t->urm ;
       if(t->vf == y)ok=true;
        }
if(ok==!true)
t->urm = p;
else
delete p ;
}


}

void dfs(int Nod){
vizitat[Nod]=1;
nod * t = L[Nod];

while(t!=nullptr)
{
    if(!vizitat[t->vf]){
        nod *q =new nod;
        q->vf = t->vf ;
        q->urm =sf;
        manevra->urm = q,manevra = q;
        dfs(t->vf);
    }

t=t->urm;
 }
}