Pagini recente » Cod sursa (job #2734044) | Cod sursa (job #3140914) | Cod sursa (job #737048) | Cod sursa (job #2183005) | Cod sursa (job #1739432)
//culori: 1 alb, 2 gri, 3 negru
#include <fstream>
using namespace std;
ifstream fin ("sortaret.in");
ofstream fout ("sortaret.out");
struct nod
{
int info;
nod * urm;
};
nod *Adj[101], *ultim[101];
int n, m;
int color[101], pred[101], d[101], f[101], time, vc[101], 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
time=time+1;
d[u]=time;
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;
time=time+1;
f[u]=time;
}
void DFS ()
{
int u;
for(u=1; u<=n; u++)
{
color[u]=1;
pred[u]=-1;
}
time=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;
}