Pagini recente » Cod sursa (job #1462609) | Cod sursa (job #2152610) | Cod sursa (job #2489995) | Cod sursa (job #896960) | Cod sursa (job #1849210)
#include <fstream>
#include <cstring>
using namespace std;
ifstream f("graf.in");
ofstream g ("graf.out");
struct nod
{
int inf;
nod *urm;
} *l[100001], *lt[100001];
int n, viz[100001], st[100001], k;
void adaug (nod *&l, int x)
{ nod *c;
c=new nod;
c->inf=x;
c->urm=l;
l=c;
}
void DF1(int i)
{
nod *c;
viz[i]=1;
for(c=l[i];c!=NULL;c=c->urm)
if (!viz[c->inf]) DF1(c->inf);
st[++k]=i;
}
void DF2(int i)
{
nod *c;
viz[i]=1; g<<i<<" ";
for(c=lt[i];c!=NULL;c=c->urm)
if (!viz[c->inf]) DF2(c->inf);
}
void DF2afij(int i)
{
nod *c;
viz[i]=1; g<<i<<" ";
fout << i << " ";
for(c=lt[i];c!=NULL;c=c->urm)
if (!viz[c->inf]) DF2(c->inf);
}
int main()
{ int i, x, y;
f>>n;
while (f>>x>>y)
{ adaug(l[x],y);
adaug(lt[y],x);
}
for (i=1; i<=n; i++)
if (!viz[i]) DF1(i);
memset (viz,0, sizeof(viz));
for (i=n; i>=1;i--)
if (!viz[st[i]])
{ DF2(st[i]);
nr++;
}
fout << nr << '\n';
for(i=1;i<=n;i++)viz[i]=0;
for (i=1; i<=n; i++)
if (!viz[i]) DF1(i);
memset (viz,0, sizeof(viz));
for (i=n; i>=1;i--)
if (!viz[st[i]])
{ DF2afij(st[i]);
g<<'\n';
}
g.close();
return 0;
}