Pagini recente » Cod sursa (job #838949) | Cod sursa (job #127150) | Cod sursa (job #466546) | Cod sursa (job #2354024) | Cod sursa (job #1887579)
#include <stdio.h>
#include <stdlib.h>
#include <vector>
using namespace std;
vector <int> v[50000];
int nrsons[50000][2];
int dfs(int nod){
int nr=0,i;
for(i=0;(unsigned int)i<v[nod].size();i++){
if(nrsons[v[nod][i]][1]!=0)
nr+=nrsons[v[nod][i]][1]+1;
else
nr+=dfs(v[nod][i])+1;
}
return nr;
}
void qSort(int egin,int nd){
int b=egin,e=nd,aux,pivot=nrsons[(egin+nd)/2][1];
while(b<=e){
while(nrsons[b][1]<pivot) b++;
while(nrsons[e][1]>pivot) e--;
if(b<=e){
aux=nrsons[b][1]; nrsons[b][1]=nrsons[e][1]; nrsons[e][1]=aux;
aux=nrsons[b][0]; nrsons[b][0]=nrsons[e][0]; nrsons[e][0]=aux;
b++; e--;
}
}
if(egin<e) qSort(egin,e);
if(b<nd) qSort(b,nd);
}
int main()
{
FILE*fin,*fout;
int n,m,i,a,b;
fin = fopen("sortaret.in" ,"r");
fout = fopen("sortaret.out" ,"w");
fscanf(fin, "%d%d" ,&n,&m);
for(i=0;i<m;i++){
fscanf(fin, "%d%d" ,&a,&b);
v[a].push_back(b);
}
for(i=1;i<=n;i++){
nrsons[i][1]=dfs(i);
//printf("%d\n" ,nrsons[i][1]);
nrsons[i][0]=i;
}
qSort(1,n);
for(i=n;i>=1;i--)
fprintf(fout, "%d\n" ,nrsons[i][0]);
return 0;
}