Cod sursa(job #705202)

Utilizator xulescuStefu Gabriel xulescu Data 3 martie 2012 18:20:38
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.08 kb
#include <fstream>
#define MAXN 50001

using namespace std;

typedef struct list{
    int nod;
    list* next;
}list;

int n,m;
list* graf[MAXN];
bool viz[MAXN];
int end[MAXN];
list* sol;
int ingrad[MAXN];

void insertsol(int nod){
    list* p = new list;
    p->nod = nod;
    p->next = sol;
    sol = p;
}

void add(int from, int to){
    list* p = new list;
    p->nod = to;
    p->next = graf[from];
    graf[from] = p;
    ingrad[to]++;
}

void dfs(int cur){
    list* p = graf[cur];
    viz[cur] = true;
    while(p){
        if(!viz[p->nod]) dfs(p->nod);
        p = p->next;
    }
    insertsol(cur);
}

int main(){
    ifstream f("sortaret.in");
    f >> n >> m;
    int a,b;
    for(int i=1; i<=m; i++){
        f >> a >> b;
        add(a,b);
    }
    f.close();

    for(int i=1;i<=n;i++){
        if(!ingrad[i]){
            dfs(i);
            break;
        }
    }

    ofstream g("sortaret.out");
    list *p = sol;
    while(p){
        g << p->nod << " ";
        p = p->next;
    }
    g.close();
    return 0;
}