Cod sursa(job #1014312)

Utilizator teoionescuIonescu Teodor teoionescu Data 22 octombrie 2013 14:15:13
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.72 kb
#include<fstream>
#include<vector>
#include<queue>
using namespace std;
ifstream in("sortaret.in");
ofstream out("sortaret.out");
const int Nmax = 50005;
vector<int> G[Nmax];
queue<int> q;
int T[Nmax],sol[Nmax];
int N,M;
int main(){
    in>>N>>M;
    for(int i=1;i<=M;i++){
        int x,y;
        in>>x>>y;
        T[y]++;
        G[x].push_back(y);
    }
    for(int i=1;i<=N;i++){
        if(!T[i]) q.push(i);
    }
    while(!q.empty()){
        int i=q.front(); q.pop();
        sol[++sol[0]]=i;
        for(vector<int>::iterator it=G[i].begin();it!=G[i].end();++it){
            T[*it]--;
            if(!T[*it]) q.push(*it);
        }
    }
    for(int i=1;i<=N;i++) out<<sol[i]<<' ';
    return 0;
}