Cod sursa(job #1498830)

Utilizator doruliqueDoru MODRISAN dorulique Data 9 octombrie 2015 14:00:25
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.33 kb
#include <iostream>
#include <fstream>

using namespace std;

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

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

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

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

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

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;
        v_predec[y]++;
        ad_el (lista_succ[x],y);
    }
    int k=1;
    int ic=1;
    while (k<=n)
    {
        while(v_predec[ic])ic=ic%n+1;
        fout<<ic<<" ";
        k++;
        v_predec[ic]=-1;
        for(q=lista_succ[ic];q;q=q->leg)//scade cu 1 numarul de predecesori ai succesorilor
            v_predec[q->nr]--;//numarului gasit
    }
    return 0;
}