Pagini recente » Cod sursa (job #1843253) | Cod sursa (job #2985900) | Cod sursa (job #1048124) | Cod sursa (job #1762701) | Cod sursa (job #145925)
Cod sursa(job #145925)
#include<fstream>
using namespace std;
int n,m;
int tfin[50001], viz[50001], t;
struct nod{
int info;
nod*urm;
} *v[100];
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;
t++;
DF(p->info);
}
p=p->urm;
}
tfin[i]=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])
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;
}