Cod sursa(job #2130021)

Utilizator matei.goantaGoanta Matei Cosmin matei.goanta Data 13 februarie 2018 13:08:04
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.99 kb
#include <fstream>
#include <vector>
#define NMAX 50005

using namespace std;

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

void citire();
void descompun();

int n, m, nr;
int gi[NMAX];
vector < vector <int> > G;


int main()
{
    citire();
    descompun();

    return 0;
}

void citire()
    {int i, x, y;
    fin>>n>>m;

    vector<int> aux;
    aux.push_back(0);

    for (i = 0; i <= n; i++)
        G.push_back(aux);
    for(i=1; i<=m; i++)
        {fin>>x>>y;
        G[x][0]++;
        G[x].push_back(y);
        gi[y]++;
        }
    }

void descompun()
    {
    int k, i, j, niv[NMAX];
    while(nr<n)
        {k=0;
        for(i=1; i<=n; i++)
            {if(gi[i]==0)
                niv[++k]=i;
            }
        nr+=k;

        for(i=1; i<=k; i++)
            {gi[niv[i]]=-1;

            fout<<niv[i]<<' ';

            for(j=1; j<=G[niv[i]][0]; j++)
                gi[G[niv[i]][j]]--;
            }
        }
    }