Cod sursa(job #1462684)

Utilizator BogdanisarBurcea Bogdan Madalin Bogdanisar Data 18 iulie 2015 18:03:37
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.92 kb
#include<iostream>
#include<fstream>
#include<cmath>
#include<algorithm>
#include<vector>
#include<bitset>
#include<cstring>
#include<queue>

#define ull unsigned long long
#define ll long long
#define pb push_back
#define FOR(a,b,c) for (int a=b;a<=c; ++a)
#define ROF(a,b,c) for (int a=b;a>=c; --a)

using namespace std;
ifstream f("sortaret.in");
ofstream g("sortaret.out");
int N,M,dimrez;
int rez[50010];
bitset<50010> verif;

struct lista {
    int val=-1;
    lista* next=NULL;
};
lista* li[50010];

void adauga(lista**,int);
void elimina(lista*,int);
void afiseaza(lista*);
void depth(int);

int main()
{
    f>>N>>M;
    FOR (i,1,N) {
        li[i]=new lista;
    }
    FOR (i,1,M) {
        int x,y;
        f>>x>>y;
        adauga(&li[x],y);
        //adauga(&li[y],x);
    }
    //afiseaza(li[2]);
    FOR (i,1,N) {
        if (!verif.test(i)) {
            depth(i);
        }
    }
    ROF (i,dimrez,1) {
        g<<rez[i]<<' ';
    }
    f.close();g.close();
    return 0;
}

void adauga(lista** v,int x) {
    lista* p=new lista;
    p->val=x;
    p->next=(*v);
    (*v)=p;
}

void elimina(lista* v,int poz) {
    if (poz==1) {
        lista* p=v->next;
        v->val=(v->next)->val;
        v->next=(v->next)->next;
        delete p;
    }
    else {
        int aux=1;
        lista* p;
        while (aux<poz && v->next!=NULL) {
            ++aux;
            p=v;
            v=v->next;
        }
        if (aux==poz) {
            p->next=v->next;
            delete v;
        }
    }
}

void afiseaza(lista* v) {
    lista* p=v;
    while (p->next!=NULL) {
        g<<p->val<<' ';
        p=p->next;
    }
    g<<'\n';
}

void depth(int i) {
    verif.set(i,1);
    lista* p=li[i];
    while (p->next!=NULL) {
        if (!verif.test(p->val)) {
            depth(p->val);
        }
        p=p->next;
    }
    rez[++dimrez]=i;
}