Pagini recente » Cod sursa (job #2420266) | Cod sursa (job #2886608) | Cod sursa (job #2792782) | Cod sursa (job #1790496) | Cod sursa (job #396662)
Cod sursa(job #396662)
#include<fstream>
using namespace std;
#define nn 100005
struct nod
{
int info;
nod *next;
};
nod *g[nn],*gt[nn],*t,*c[nn];
int v[nn],vt[nn],nrc,final[nn],timp,n,m;
void adauga(nod *g[],int a,int b)
{
t=new nod;
t->info=b;
t->next=g[a];
g[a]=t;
}
void dfs(int vf)
{
v[vf]=1;
for(t=g[vf];t;t=t->next)
if(!v[t->info])
dfs(t->info);
final[++timp]=vf;
}
void dfst(int x,int nrc)
{
vt[x]=1;
t=new nod;
t->info=x;
t->next=c[nrc];
c[nrc]=t;
for(t=g[x];t;t=t->next)
if(!vt[t->info])
dfst(t->info,nrc);
}
void kosaraju()
{
for(int i=1;i<=n;++i)
if(v[i])
dfs(i);
for(int i=timp;i;--i)
if(vt[i])
dfst(final[i],++nrc);
}
int main()
{
ifstream fin("ctc.in");
fin>>n>>m;
int a,b;
for(;m;--m)
{
fin>>a>>b;
adauga(g,a,b);
adauga(gt,b,a);
}
fin.close();
kosaraju();
FILE *f=fopen("ctc.out","w");
fprintf(f,"%d\n",nrc);
for(int i=1;i<=nrc;++i)
{
for(t=c[i];t;t=t->next)
fprintf(f,"%d ",t->info);
fprintf(f,"\n");
}
fclose(f);
return 0;
}