Pagini recente » Cod sursa (job #646087) | Cod sursa (job #2002060) | Cod sursa (job #1889744) | Cod sursa (job #1572969) | Cod sursa (job #1497846)
#include <iostream>
#include <fstream>
using namespace std;
ifstream fin ("sortaret.in");
ofstream fout ("sortaret.out");
struct succesor
{
int nr;
succesor *leg;
}*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
{
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;
}