Cod sursa(job #482904)

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

using namespace std;

vector<int> v[nmax];
int viz[nmax], c[nmax], l[nmax], nr[nmax];
int ul = 0;

void dfs(int nod){
    viz[nod] = 1;
    for (int i = 0; i < v[nod].size(); i++)
        if (viz[v[nod][i]] == 0)
            dfs(v[nod][i]);
    ul++;
    l[ul] = nod;  
}

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[u].push_back(p);
        nr[p]++;
    }
    
    p = 1;
    u = 0;
    for (i = 1; i <= n; i++)
        if (nr[i] == 0){
            u++;
            c[u] = i;
        }
        
    for (i = 1; i <= u; i++)
        dfs(c[i]);  
    
    for (i = 1; i <= ul; i++)
        g<<l[i]<<" ";
    g<<'\n';
    
    return 0;
}