Cod sursa(job #1921735)

Utilizator nicu_serteSerte Nicu nicu_serte Data 10 martie 2017 14:03:13
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.88 kb
#include <fstream>
#include <vector>
using namespace std;
ifstream fin("sortaret.in");
ofstream fout("sortaret.out");
vector <int> g[50001];
int n, deg[50001]={0}, q[50001];
void citire()
{
    int m, i, j;
    fin>>n>>m;
    while(m)
    {
        m--;
        fin>>i>>j;
        g[i].push_back(j);
        deg[j]++;
    }
    fin.close();
}
void sortare()
{
    vector <int> :: iterator it;
    int k, i;
    for(i=1; i<=n; i++)
        if(!deg[i])
            q[++q[0]]=i;
    for(i=1; i<=n; i++)
    {
        k=q[i];
        for(it=g[k].begin(); it!=g[k].end(); it++)
        {
            deg[*it]--;
            if(!deg[*it])
                q[++q[0]]=*it;
        }
    }
}
void afisare()
{
    for(int i=1; i<=n; i++)
        fout<<q[i]<<' ';
    fout.close();
}
int main()
{
    citire();
    sortare();
    afisare();
    return 0;
}