Cod sursa(job #1219337)

Utilizator andreimdvMoldovan Andrei andreimdv Data 14 august 2014 00:14:14
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.23 kb
//Sortare topologica pe graf orientat aciclic
// Sortare in care daca exista un arc ( i, j ), atunci i apare inaintea lui j in aceasta ordonare
// facem o parcurgere in latime, eliminand nodurile pe rand, daca au gradul interior 0
#include<fstream>
#include<vector>
using namespace std;


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

int i,n,m,a,b,gradint[50005],aux;
vector<int>coada;

vector<int> v[50005];
vector<int> ::iterator itr;

void toposort()
{
    for(i=1;i<=n;++i)
    {
        if(gradint[i]==0)
        {
            coada.push_back(i); // pentu ca este aciclic tot timpul va intra aici
        }
    }
    for(i=0;i<n;++i)
    {
        aux=coada[i];
        for(itr=v[aux].begin();itr!=v[aux].end();itr++)
        {
            gradint[*itr]--;
            if(gradint[*itr]==0)
            {
                coada.push_back(*itr); // nu avem nevoie de vizitat[] pentru ca daca gradul int este 0 nu se va mai ajunge la acel nod
            }
        }
    }
}

int main()
{
    fin>>n>>m;
    for(i=1;i<=m;++i)
    {
        fin>>a>>b;
        gradint[b]++;
        v[a].push_back(b);
    }
    toposort();
    for(i=0;i<n;++i)
    fout<<coada[i]<<" ";



    return 0;
}