Cod sursa(job #1912341)

Utilizator duesakBourceanu Cristian duesak Data 8 martie 2017 01:24:07
Problema Sortare topologica Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 0.71 kb
#include<fstream>
using namespace std;
ifstream fin("sortaret.in");
ofstream fout("sortaret.out");
int deg[50001],q[50001];
int ma[50001][9000];
void topsort(int n){
    int i,nd,j;
    for(i=1;i<=n;i++)
        if(deg[i]==0)q[++q[0]]=i;
    for(i=1;i<=n;i++){
        nd=q[i];
        for(j=1;j<=ma[nd][0];j++){
            deg[ma[nd][j]]--;
            if(deg[ma[nd][j]]==0)q[++q[0]]=ma[nd][j];
        }
    }
}
int main(void){
    int n,m,a,b;
    fin>>n>>m;
    for(int i=1;i<=m;i++){
        fin>>a>>b;
        ma[a][++ma[a][0]]=b;
        deg[b]++;
    }
    topsort(n);
    for(int i=1;i<=n;i++)
        fout<<q[i]<<" ";
    fout<<'\n';
    fin.close();
    fout.close();
    return 0;
}