Cod sursa(job #627220)

Utilizator Luncasu_VictorVictor Luncasu Luncasu_Victor Data 29 octombrie 2011 12:34:26
Problema Sortare topologica Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 1.06 kb
#include <stdio.h>
int n,m;
struct nod{
    int y;
    struct nod*next; }*g[50001];

struct stiv{
    int y;
    struct stiv*next;
    struct stiv*pred; }*a,*b;
bool viz[50001];

void add(int x,int y){
    nod*a=new nod;
    a->y=y;
    a->next=g[x];
    g[x]=a;
}

void read_data(){
    int i,x,y;
        freopen("sortaret.in","r",stdin);
        scanf("%d%d",&n,&m);
    for(i=1;i<=m;i++){
        scanf("%d%d",&x,&y);
            add(x,y);}
}

void DFS(int x){
    viz[x]=1;
    stiv*c; nod*v=g[x];
    c=new stiv; c->y=x; c->pred=b; c->next=NULL; b->next=c; b=c;
    while(v!=NULL){
        DFS(v->y);
        v=v->next;};
}

void process(){
    int i;
    a=new stiv; a->y=-1; b=a;
    for(i=1;i<=n;i++)
    if(!viz[i])DFS(i);
}

void write_data(stiv*b){
    while(b->y!=-1){
        if(viz[b->y]){
            viz[b->y]=0;
            write_data(b);
            printf("%d ",b->y);}
        b=b->pred;
    }
}

int main(){
    read_data();
    process();
    freopen("sortaret.out","w",stdout);
    write_data(b);
}