Cod sursa(job #1048561)

Utilizator buzu.tudor67Tudor Buzu buzu.tudor67 Data 6 decembrie 2013 01:07:51
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.69 kb
#include<fstream>
#define maxn 50005
using namespace std;
ifstream fi("sortaret.in");
ofstream fo("sortaret.out");

struct nod{
       int info;
       nod *next;
       };

int n,m,i,x,y,level;
int d[maxn],b[maxn];
nod *a[maxn],*q;

void dfs(int k){
     nod *q;
     q=a[k]; level++;
     
     while(q!=NULL) {
                     if (b[q->info]<level) {
                                            b[q->info]=level;
                                            dfs(q->info);
                                           }
                     q=q->next;
                    }
}

void swap2(int i,int j){
     int x;
     x=b[i]; b[i]=b[j]; b[j]=x;
     x=d[i]; d[i]=d[j]; d[j]=x;
}

void quick(int left,int right){
     int mid,i,j;
     mid=b[(left+right)/2];
     i=left; j=right;
     
     while (i<j){
                 while (b[i]<mid) i++;
                 while (b[j]>mid) j--;
                 if (i<=j) {
                            swap2(i,j);
                            i++; j--;
                           }
                 }
     if (i<right) quick(i,right);
     if (left<j) quick(left,j);
}

int main(){
    fi>>n>>m;
    
    for(i=1;i<=n;i++) { a[i]=NULL; d[i]=i; }
    
    for(i=1;i<=m;i++){
                      fi>>x>>y;
                      q=new nod;
                      q->info=y;
                      q->next=a[x];
                      a[x]=q;
                     }

    for(i=1;i<=n;i++) 
       if(b[i]==0){
                   level=0;
                   dfs(i);
                  }
    
    quick(1,n);
    for(i=1;i<=n;i++) fo<<d[i]<<" ";
                     
    fi.close();
    fo.close();
    return 0;
}