Pagini recente » Cod sursa (job #1411654) | Cod sursa (job #2301276) | Cod sursa (job #73720) | Cod sursa (job #884873) | Cod sursa (job #1980308)
#include <stdint.h>
#include <fstream>
#include <stdlib.h>
#define nmax 50001
#define mmax 100001
using namespace std;
fstream f1("sortaret.in", ios::in);
fstream f2("sortaret.out", ios::out);
int32_t n, m, v[mmax*2], aux[nmax], cap[nmax], stiva[nmax], vf;
int16_t viz[nmax];
///lista de adacenta
struct muchii
{
int32_t x, y;
}muc[mmax];
struct nod
{
nod* urm;
int32_t info;
} l[nmax], * prim;
void citire()
{
int32_t i, x, y;
f1>>n>>m;
for(i=1; i<=m; i++)
{
f1>>x>>y;
muc[i].x=x;
muc[i].y=y;
aux[x]++;
}
cap[1]=1;
for(i=2; i<=n; i++)
{
cap[i]= cap[i-1]+ aux[i-1];
aux[i-1]=cap[i-1];
}
aux[i-1]=cap[i-1];
for(i=1; i<=m; i++)
{
x=muc[i].x;
y=muc[i].y;
v[aux[x]]=y;
aux[x]++;
}
}
void dfs(int32_t nod)
{
int32_t i;
viz[nod]=1;
for(i=cap[nod]; i<cap[nod+1]; i++)
if(!viz[v[i]])
{
viz[v[i]]=1;
dfs(v[i]);
vf++;
stiva[vf]=v[i];///adaugi nodurile la lista in ordine inversa
}
}
void adauga()
{
int32_t i;
for(i=1; i<=vf; i++)
{
//adaugi nodul stiva[i] in fata listei l
nod *p= new nod;
p->info=stiva[i];
p->urm=prim;
prim=p;
}
}
void sortare()
{
int32_t i;
for(i=1; i<=n; i++)
if(!viz[i])
{
vf=0;
dfs(i);
vf++;
stiva[vf]=i;
adauga();///adaugi el stivei in fata listei rezultat
}
}
void afisare()
{
nod *p;
for(p=prim; p!=0; p=p->urm)
f2<<p->info<<" ";
}
int main()
{
citire();///+lista adiacenta
sortare();
afisare();
return 0;
}