Cod sursa(job #1498519)

Utilizator GuzgleteBumbu Alexandru Guzglete Data 8 octombrie 2015 18:28:42
Problema Sortare topologica Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 1.77 kb
#include <iostream>
#include <fstream>

using namespace std;

ifstream fin ("sortaret.in");
ofstream fout ("sortaret.out");

struct succesor
{
    int nr;
    succesor *leg;
}*lista_succ[100000]; //listele succesorilor fiecarui element

int v_predec[100000]; //numarul predecesorilor fiecarui element

void ad_el (succesor *&p, int x) //adauga element la sfarsitul listei
{
    if (p==0)
    {
        p=new succesor;
        p->nr=x;
        p->leg=0;
    }
    else
    {
        succesor *aux;
        for (aux=p;aux->leg!=0;aux=aux->leg);
        succesor *q;
        q=new succesor;
        q->nr=x;
        q->leg=0;
        aux->leg=q;
    }
}

int caut (succesor *p,int x) //cauta un element in lista. returneaza 1 daca a gasit si 0 daca nu
{
    if (p==0) return 0;
    if (p->nr==x) return 1;
    return caut (p->leg,x);
}

int pozmin (int v[50010], int n, int i) //afla pozitia minimului din sir
{
    if (i==n) return n;
    if (v[i] <= v[pozmin(v,n,i+1)]) return i;
    return pozmin (v,n,i+1);
}

int main()
{
    int n,p,x,y;
    fin>>n;
    fin>>p;
    for (int i=1;i<=p;i++)
    {
        fin>>x>>y;
        if (caut (lista_succ[x],y) == 0)
        {
            v_predec[y]++;
            ad_el (lista_succ[x],y);
        }
    }

    while (v_predec[pozmin(v_predec,n,1)] != n+1)
    {
        fout<<pozmin(v_predec,n,1)<<" ";       //este gasit numarul cu cei mai putin predecesori
        succesor *q=lista_succ[pozmin(v_predec,n,1)];
        v_predec[pozmin(v_predec,n,1)]=n+1;
        while (q)                   //scade cu 1 numarul de predecesori ai succesorilor numarului gasit
        {
            if (v_predec[q->nr]!=n+1) v_predec[q->nr]--;
            q=q->leg;
        }
    }


    return 0;
}