Pagini recente » Cod sursa (job #3163836) | Cod sursa (job #1159443) | Cod sursa (job #156322) | Cod sursa (job #697722) | Cod sursa (job #1739394)
//culori: 1 alb, 2 gri, 3 negru
#include <fstream>
#include <iostream>
using namespace std;
ifstream fin ("sortaret.in");
ofstream fout ("sortaret.out");
struct nod
{
int info;
nod * urm;
};
nod *Adj[50001], *ultimul[50001];
int n, m;
int color[50001], pred[50001], d[50001], f[50001], time;
nod *ultim;
nod *sorted;
void afisare_lista (nod *q)
{
while(q!=NULL)
{
fout<<q->info<<' ';
q=q->urm;
}
}
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++)
ultimul[i]=NULL;
for(i=1; i<=m; i++)
{
fin>>x>>y;
adaugare(y, Adj[x], ultimul[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.
fout<<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);
}
void topological_sort ()
{
DFS ();
}
int main()
{
creare();
topological_sort();
return 0;
}