Pagini recente » Cod sursa (job #856252) | Cod sursa (job #2104233) | Cod sursa (job #114992) | Cod sursa (job #2157385) | Cod sursa (job #677287)
Cod sursa(job #677287)
#include<fstream>
using namespace std;
struct nod{int info;nod*adr;}*v[100003],*vt[100003],*p;
int n,m,i,x,y;
short viz[100003];
int ord[100003],nr=0,nrctc;
int ctc[200003];
void dfs(int nod)
{
viz[nod]=1;
while(v[nod])
{
if(!viz[v[nod]->info])dfs(v[nod]->info);
v[nod]=v[nod]->adr;
}
ord[++nr]=nod;
}
void dfst(int nod)
{
viz[nod]=0;
ctc[++nr]=nod;
while(vt[nod])
{
if(viz[vt[nod]->info])dfst(vt[nod]->info);
vt[nod]=vt[nod]->adr;
}
}
int main()
{
ifstream f("ctc.in");ofstream g("ctc.out");
f>>n>>m;
for(i=1;i<=m;i++)
{
f>>x>>y;
p=new nod;
p->info=y; p->adr=v[x]; v[x]=p;
p=new nod;
p->info=x; p->adr=vt[y]; vt[y]=p;
}
for(i=1;i<=n;i++)
if(!viz[i])
dfs(i);
nr=0;
for(i=n;i>=1;i--)
if(viz[ord[i]])
{
dfst(ord[i]);
ctc[++nr]=0;
nrctc++;
}
g<<nrctc<<'\n';
i=1;
while(nrctc)
{
while(ctc[i]){ g<<ctc[i]<<" ";i++; }
i++;
nrctc--;
g<<'\n';
}
f.close();g.close();
return 0;}