Cod sursa(job #214249)

Utilizator catalina5catalina serban catalina5 Data 13 octombrie 2008 17:16:47
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.89 kb
#include<iostream>
#include<fstream>
#include<vector>

using namespace std;

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

int n,m,grex[50001],fn[50001],nfn=1;
vector<int>st[50001];

void citire(){
    int n1,n2;
    fin>>n>>m;
    for(int i=0;i<m;i++){
        fin>>n1>>n2;
        grex[n2]++;
        st[n1].push_back(n2);
    }
}

void sort_top(){
    for(int i=1;i<=n;i++)
        if(grex[i]==0)
            fn[nfn++]=i;
    for(int i=1;i<=n;i++){
        int k=fn[i];
        for(vector<int>::iterator it=st[k].begin();it!=st[k].end();it++){
            grex[(*it)]--;
            if(!grex[(*it)])
                fn[nfn++]=(*it);
        }
    }
}

void afis(){
    for(int i=1;i<=n;i++)
        fout<<fn[i]<<" ";
    fout<<"\n";
}

int main(){
    citire();
    sort_top();
    afis();
    fin.close();
    fout.close();
    return 0;
}