Pagini recente » Cod sursa (job #1010628) | Cod sursa (job #631030) | Cod sursa (job #1226254) | Cod sursa (job #2625798) | Cod sursa (job #1498794)
#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;
int a = pozmin(v,n,i+1);
if (v[i] <= v[a])
return i;
return a;
}
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)];
if (v_predec[pozmin(v_predec,n,1)]==0) 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;
}
}
/**for(int i = 1; i <= n; ++i)
for(int j = 1; j <= n; ++j)
if(not v_predec[j]) {
v_predec[j] = -1;
fout << j << " ";
succesor *P = lista_succ[j];
while(P){
-- v_predec[P->nr];
P = P->leg;
}
break;
}**/
return 0;
}