Cod sursa(job #482903)

Utilizator andra23Laura Draghici andra23 Data 5 septembrie 2010 22:41:44
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.85 kb
#include<fstream>
#include<vector>
#define nmax 50005

using namespace std;

vector<int> v[nmax];
int c[nmax], nr[nmax];

int main(){
    ifstream f("sortaret.in");
    ofstream g("sortaret.out");
    int m, n;
    f>>n>>m;
    int i, j, p, u, x;
    
    for (i = 1; i <= m; i++){
        f>>p>>u;
        v[p].push_back(u);
        nr[u]++;
    }    
    
    p = 1;
    u = 0;
    for (i = 1; i <= n; i++)
        if (nr[i] == 0){
            u++;
            c[u] = i;
        }
    
    while (p <= u){
        x = c[p];
        p++;
        for (i = 0; i < v[x].size(); i++){
            nr[v[x][i]]--;
            if (nr[v[x][i]] == 0){
                u++;
                c[u] = v[x][i];
            }
        }   
    }
    
    for (i = 1; i <= n; i++)
        g<<c[i]<<" ";
    g<<'\n';
    
    return 0;
}