Cod sursa(job #1887579)

Utilizator david.sachelarieDavid Sachelarie david.sachelarie Data 21 februarie 2017 17:51:25
Problema Sortare topologica Scor 90
Compilator cpp Status done
Runda Arhiva educationala Marime 1.29 kb
#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;
}