Pagini recente » Cod sursa (job #1318090) | Cod sursa (job #1616470) | Cod sursa (job #94864) | Cod sursa (job #1197968) | Cod sursa (job #1739437)
//culori: 1 alb, 2 gri, 3 negru
#include <fstream>
#define NMAX 50001
using namespace std;
ifstream fin ("sortaret.in");
ofstream fout ("sortaret.out");
struct nod
{
int info;
nod * urm;
};
nod *Adj[NMAX], *ultim[NMAX];
int n, m;
int color[NMAX], pred[NMAX], d[NMAX], f[NMAX], timp, vc[NMAX], k;
void adaugare (int x, nod *&prim, nod *&ultim)
{
nod *p;
p=new nod;
p->info=x;
p->urm=NULL;
if(prim==NULL)
prim=ultim=p;
else
{
ultim->urm=p;
ultim=p;
}
}
void creare ()
{
int x, i, y;
fin>>n>>m;
for(i=1; i<=n; i++)
ultim[i]=NULL;
for(i=1; i<=m; i++)
{
fin>>x>>y;
adaugare(y, Adj[x], ultim[x]);
}
}
void DFS_VISIT (int u)
{
color[u]=2; //White vertex u has just been discovered
timp=timp+1;
d[u]=timp;
int v;
nod *p;
p=new nod;
p=Adj[u];
while(p!=NULL)
{
v=p->info; //Explore edge (u,v).
if(color[v]==1)
{
pred[v]=u;
DFS_VISIT(v);
}
p=p->urm;
}
color[u]=3; //Blacken u; it is finished.
vc[++k]=u;
timp=timp+1;
f[u]=timp;
}
void DFS ()
{
int u;
for(u=1; u<=n; u++)
{
color[u]=1;
pred[u]=-1;
}
timp=0;
for(u=1; u<=n; u++)
if(color[u]==1)
DFS_VISIT(u);
}
int main()
{
creare();
DFS();
for(int i=k;i>=1;i--)
fout<<vc[i]<<' ';
return 0;
}