Pagini recente » Cod sursa (job #804897) | Cod sursa (job #1935706) | Cod sursa (job #2512628) | Cod sursa (job #2507635) | Cod sursa (job #396685)
Cod sursa(job #396685)
#include<fstream>
#include<iostream>
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)
{
//cout<<vf<<" ";cout.flush();
v[vf]=1;
for(nod *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]=nrc;
t=new nod;
t->info=x;
t->next=c[nrc];
c[nrc]=t;
for(nod *t=gt[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),cout<<endl;
//cout<<"2\n";cout.flush();
for(int i=timp ; i ; --i)
if(!vt[final[i]])
dfst(final[i],++nrc);
}
void afis(nod * G[]){
for(int i=1;i<=n;++i){
cout<<i<<" : ";
for(nod *p=G[i]; p ; p=p->next)
cout<<p->info<<" ";
cout<<endl;
}
}
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);
}
//afis(g);
//afis(gt);
// cout<<"1\n";cout.flush();
fin.close();
kosaraju();
//cout<<"1\n";cout.flush();
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;
}