Cod sursa(job #2065225)

Utilizator danielsociuSociu Daniel danielsociu Data 13 noiembrie 2017 16:50:55
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.79 kb
#include <fstream>
#include <vector>
using namespace std;
ifstream cin("sortaret.in");
ofstream cout("sortaret.out");
#define NMAX 50100
int m,n,rep[NMAX],rez[NMAX]; vector<int> we[NMAX];

void read(){
    cin>>n>>m;
    int a,b;
    while(m){
        cin>>a>>b; we[a].push_back(b); rep[b]++; --m;
    }
}

void solve(){
    int i,x; vector<int>::iterator it;
    for(i=1; i<=n; i++)
        if(rep[i]==0)
            rez[++rez[0]]=i;
    for(i=1;i<=n;i++){
        x=rez[i];
        for(it=we[x].begin(); it!=we[x].end(); ++it){
            --rep[*it];
            if(rep[*it]==0) rez[++rez[0]] = *it;
        }
    }

}

void write(){
    for(int i=1;i<=n;i++){
        cout<<rez[i];
    }
}

int main(){
    read();
    solve();
    write();
    return 0;
}