Cod sursa(job #993360)

Utilizator vicciuvic ciu vicciu Data 3 septembrie 2013 18:09:49
Problema Sortare prin comparare Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.71 kb
#include "stdio.h"
#include <vector>

using namespace std;

FILE *in,*out;
int i,j,k,l,m,n;
int a[100000],b[100000],d[50000],f[50000];
vector <int> c[50000];
vector <int> nex;
bool e[50000];

int main()
{
        for (i=0; i<50000; i++)
        {
            d[i]=0;
            e[i]=false;
        }
    k=0;
    in=fopen("sortaret.in","r");
    fscanf(in,"%d %d",&n,&m);
        for (i=0; i<m; i++)
        {
            fscanf(in,"%d %d",&a[i],&b[i]);
            c[b[i]-1].push_back(a[i]-1);
            d[a[i]-1]++;
        }
    fclose(in);
        for (i=0; i<n; i++)
        if (d[i]==0) nex.push_back(i);

        for (j=0; j<n; j++)
        {
            if (nex.size()==0)
            {
            for (i=0; i<n; i++)
            {
                if ((d[i]==0) && (e[i]==false))
                {
                    e[i]=true;
                    f[k]=i;
                    k++;
                        for (l=0; l<c[i].size(); l++)
                        {
                            d[c[i][l]]--;
                            if (d[c[i][l]]==0) nex.push_back(c[i][l]);
                        }
                    break;
                }
            }
            } else
            {
                i=nex[nex.size()-1];
                nex.pop_back();
                e[i]=true;
                f[k]=i;
                k++;
                    for (l=0; l<c[i].size(); l++)
                    {
                        d[c[i][l]]--;
                        if (d[c[i][l]]==0) nex.push_back(c[i][l]);
                    }
            }
        }
    out=fopen("sortaret.out","w");
        for (i=n-1; i>=0; i--)
        fprintf(out,"%d ",f[i]+1);
    return 0;
}