Cod sursa(job #146078)

Utilizator MciprianMMciprianM MciprianM Data 1 martie 2008 10:05:44
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.2 kb
#include<fstream>
using namespace std;
int n,m;
int tfin[50001], viz[50001], t;
struct nod{
  int info;
  nod*urm;
} *v[50001];

void add(int x, int y){
  nod* p;
  p=new nod;
  p->info=y;
  p->urm=v[x];
  v[x]=p;
}

void DF(int i){
  nod* p=v[i];
  while(p){
    if(!viz[p->info]){
      viz[p->info]=1;
      DF(p->info);
    }
    p=p->urm;
  }
  tfin[i]=t;t++;
}
int part(int st, int dr){
  int ii=0, jj=-1;
  int i=st, j=dr;
  int aux;
  while(i<j){
    if(tfin[i]<tfin[j]){
      aux=tfin[i];
      tfin[i]=tfin[j];
      tfin[j]=aux;
      aux=viz[i];
      viz[i]=viz[j];
      viz[j]=aux;
      aux=ii;
      ii=-jj;
      jj=-aux;
    }
    i=i+ii;
    j=j+jj;
  }
  return i;
}
void qsort(int i, int j){
  if(i<j){
    int m=part(i,j);
    qsort(i,m-1);
    qsort(m+1,j);
  }
}
int main(){
  int x,y,i;
  ifstream f("sortaret.in");
  f>>n>>m;
  for(i=0;i<=m;i++){
    f>>x>>y;
    add(x,y);
  }
  f.close();
  for(i=1;i<=n;i++)
    if(!viz[i]){
      viz[i]=1;
      DF(i);
    }
  for(i=1;i<=n;i++)
    viz[i]=i;
  qsort(1,n);
  ofstream g("sortaret.out");
  for(i=1;i<=n;i++)
    g<<viz[i]<<' ';
  g<<'\n';
  g.close();
  return 0;
}