Cod sursa(job #1686851)

Utilizator savinvadim1312savin vadim savinvadim1312 Data 12 aprilie 2016 14:39:11
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.67 kb
#include <iostream>
#include <fstream>

using namespace std;

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

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

struct lista *L_p,*L_u,*L_c,*S_p,*S_c,*S_u;

int n,m,t[5000][5000],x,y,d;

bool margine(int x){
    for(int i=0;i<n;i++){
        if(t[i][x]==1)
            return false;
    }
    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;
    }
}
void adauga_2(int x){
        if(S_p == NULL){
        S_p = new lista;
        S_p->val = x;
        S_p->next = NULL;
        S_u = new lista;
        S_u = S_p;
    }
    else{
        S_c = new lista;
        S_c->val = x;
        S_c->next = NULL;
        S_u->next = S_c;
        S_u = S_c;
    }
}

int main()
{
    f>>n>>m;
    for(int i=0;i<m;i++){
        f>>x>>y;
        t[x-1][y-1] = 1;
    }

    for(int i=0;i<n;i++){
        if(margine(i)){
            adauga(i);
        }
    }

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

        for(int i=0;i<n;i++){
            if(t[d][i] != 0){
                t[d][i] = 0;
                if(margine(i)){
                    adauga(i);
                }
            }
        }
    }

    S_c = S_p;
    while(S_c != NULL){
        g<<S_c->val+1<<" ";
        S_c = S_c->next;
    }



    return 0;
}