Pagini recente » Cod sursa (job #111435) | Cod sursa (job #1961772) | Cod sursa (job #2362597) | Cod sursa (job #2382238) | Cod sursa (job #1980331)
#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], gin[nmax], cap[nmax], stiva[nmax], vf, nrm=1;
int16_t viz[nmax];
///lista de adacenta
struct muchii
{
int32_t x, y;
}muc[mmax];
int16_t found(int32_t x, int32_t y)
{
int32_t i;
for(i=1; i<= nrm; i++)
if((muc[i].x==x)&&(muc[i].y==y)) return 1;
return 0;
}
void citire()
{
int32_t i, x, y;
f1>>n>>m;
for(i=1; i<=m; i++)
{
f1>>x>>y;
if(!found(x, y))
{
muc[nrm].x=x;
muc[nrm].y=y;
nrm++;
}
///elimini muchiile duble
}
m=nrm-1;
for(i=1; i<=m; i++)
{
aux[muc[i].x]++;
gin[muc[i].y]++;
}
cap[1]=1;
for(i=2; i<=n+1; i++)
{
cap[i]= cap[i-1]+ aux[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 sortare2()
{
int32_t i, j, temp;
///bagi in stiva nodurile cu grad interior 0
for(i=1; i<=n; i++)
if(!gin[i]) {vf++; stiva[vf]=i; viz[i]=1;}
while(vf!=0)
{
//iei un nod din stiva, il afisezi
//decr gin vecinilor si il elimini
f2<<stiva[vf]<<" ";
temp=stiva[vf];
vf--;///necesar inainte ca sa nu analizezi de 2 ori acelasi nod
for(j=cap[temp]; j<cap[temp+1]; j++)
if(!viz[v[j]])
{
gin[v[j]]--;
if(!gin[v[j]]) {vf++; stiva[vf]=v[j]; viz[v[j]]=1;}
}
}
}
int main()
{
citire();///+lista adiacenta
sortare2();
return 0;
}