Cod sursa(job #1687643)

Utilizator savinvadim1312savin vadim savinvadim1312 Data 12 aprilie 2016 23:39:05
Problema Sortare topologica Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 2.02 kb
#include <iostream>
#include <fstream>

using namespace std;

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

struct lista{
    int val;
    lista *next;
};

struct graf{
    int f,t;
    graf *next;
};

struct lista *L_p,*L_u,*L_c;
struct graf *p, *u, *c;

int n,m,d;

void citire(){
    f>>n>>m;
    for(int i=0;i<m;i++){
        if(p == NULL){
            p = new graf;
            p->next = NULL;
            f>>p->f>>p->t;
            u = p;

        }
        else{
            c = new graf;
            c->next = NULL;
            f>>c->f>>c->t;
            u->next = c;
            u=c;
        }
    }
}

bool margine(int x){
    c = p;
    while(c!=NULL){
        if(c->t == x){
            return false;
        }
        c = c->next;
    }
    return true;
}

void adauga(int x){
    if(L_p == NULL){
        L_p = new lista;
        L_p->val = x;
        L_p->next = NULL;
        L_u = new lista;
        L_u = L_p;
    }
    else{
        L_c = new lista;
        L_c->val = x;
        L_c->next = NULL;
        L_u->next = L_c;
        L_u = L_c;
    }
}

bool sterge(int x, int y){
    if(p==NULL){
        return false;
    }
    c = p;
    u = p;
    if(p->f == x && p->t == y){
        p = p->next;
        delete c;
        return true;
    }
    c = p;
    while(c!=NULL){
        if(x == c->f && y == c->t){
            u->next = c->next;
            delete c;
            return true;
        }
        u=c;
        c = c->next;
    }
    return false;
}

int main()
{
    citire();
    for(int i=1;i<=n;i++){
        if(margine(i)){
            adauga(i);
        }
    }

    while(L_p != NULL){
        d = L_p->val;
        g<<d<<" ";
        L_c = L_p;
        L_c = L_p;
        L_p = L_p->next;
        delete L_c;

        for(int i=1;i<=n;i++){
            if(sterge(d,i)){
                if(margine(i)){
                    adauga(i);
                }
            }
        }
    }

    return 0;
}