Cod sursa(job #1912350)

Utilizator duesakBourceanu Cristian duesak Data 8 martie 2017 01:46:10
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.91 kb
#include<fstream>
#include<vector>
using namespace std;
ifstream fin("sortaret.in");
ofstream fout("sortaret.out");
int deg[50001],q[50001];
//int ma[50001][9000];
vector<int>ma2[50002];
void topsort(int n){
    int i,nd;
    vector<int>::iterator it;
    for(i=1;i<=n;i++)
        if(deg[i]==0)q[++q[0]]=i;
    for(i=1;i<=n;i++){
        nd=q[i];
        for(it=ma2[nd].begin();it!=ma2[nd].end();++it){
            //deg[ma[nd][j]]--;
            //if(deg[ma[nd][j]]==0)q[++q[0]]=ma[nd][j];
            deg[*it]--;
            if(deg[*it]==0)q[++q[0]]=*it;
        }
    }
}
int main(void){
    int n,m,a,b;
    fin>>n>>m;
    for(int i=1;i<=m;i++){
        fin>>a>>b;
        ma2[a].push_back(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;
}