Pagini recente » Cod sursa (job #1738974) | Rating zaharia (zaha1234) | Cod sursa (job #1105313) | Cod sursa (job #498249) | Cod sursa (job #472615)
Cod sursa(job #472615)
#include<fstream.h>
#include<list>
#define Nmax 100009
using namespace std;
typedef list<long> LI;
typedef LI::iterator IT;
LI a[Nmax],at[Nmax];
long n,m,nrc,v[Nmax],po[Nmax],nr;
void cit()
{ifstream fin("ctc.in");
fin>>n>>m;
long i,x,y;
for(i=1;i<=m;++i)
{fin>>x>>y;
a[x].push_back(y);
at[y].push_back(x);
}
fin.close();
}
void dfs(long k)
{IT it;
v[k]=1;
for(it=a[k].begin();it!=a[k].end();++it)
if(v[*it]==0)
dfs(*it);
++nr;po[nr]=k;
}
void dfst(long k)
{IT it;
v[k]=-nrc;
for(it=at[k].begin();it!=at[k].end();++it)
if(v[*it]==1)
dfst(*it);
}
ofstream fout("ctc.out");
void dfstafis(long k)
{IT it;
v[k]=-nrc;
fout<<k<<" ";
for(it=at[k].begin();it!=at[k].end();++it)
if(v[*it]==1)
dfstafis(*it);
}
void afis()
{long i,j;
for(i=1;i<=n;++i)
if(v[i]==0)
dfs(i);
for(i=n;i>=1;--i)
if(v[po[i]]==1)
{++nrc;
dfst(po[i]);
}
fout<<nrc<<'\n';
for(i=1;i<=n;++i)
v[i]=1;
nrc=0;
for(i=n;i>=1;--i)
if(v[po[i]]==1)
{++nrc;
dfstafis(po[i]);
fout<<'\n';
}
fout.close();
}
int main()
{cit();
afis();
return 0;
}