Cod sursa(job #1335315)

Utilizator Arodoet96Teodora Stoleru Arodoet96 Data 5 februarie 2015 13:22:15
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.1 kb
#include <fstream>
#include <vector>
#define DMAX 50004

using namespace std;

ifstream fin("sortaret.in");
ofstream fout("sortaret.out");

int n, m;
int di[DMAX];
vector <int> A[DMAX];
int C[2][DMAX], crt, urm;

void citire();
void sortare_topologica();

int main()
{
    citire();
    sortare_topologica();
    return 0;
}

void citire()
{
    int i, x, y;
    fin>>n>>m;
    for(i=1;i<=m;i++)
    {
        fin>>x>>y;
        A[x].push_back(y);
        di[y]++;
    }
}

void sortare_topologica()
{
    int i, j, lg;
    crt=0; urm=1;

    C[crt][0]=0;
    for(i=1;i<=n;i++)
        if(!di[i])
            C[crt][++C[crt][0]]=i;

    do{
        for(i=1;i<=C[crt][0];i++)
        {
            fout<<C[crt][i]<<' ';
            di[C[crt][i]]=-1;

            lg=A[C[crt][i]].size();
            for(j=0;j<lg;j++)
            {
                di[A[C[crt][i]][j]]--;
                if(!di[A[C[crt][i]][j]])
                    C[urm][++C[urm][0]]=A[C[crt][i]][j];
            }
        }

        crt=1-crt; urm=1-urm; C[urm][0]=0;

    }while(C[crt][0]);
}