Pagini recente » Cod sursa (job #276141) | Cod sursa (job #3190475) | Cod sursa (job #628304) | Cod sursa (job #113172) | Cod sursa (job #363186)
Cod sursa(job #363186)
#include<fstream>
#define nmax 100001
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
int n,m,numar=1;
int nr,viz[nmax],postordine[nmax];
int comp[nmax];
struct nod
{int inf; //valoarea nodului respectiv
nod *urm; //adresa urmatorului nod din lista
};
nod *l[nmax],*a[nmax];
void citire()
{int i,m,x,y;
fin>>n>>m;
for(i=1;i<=m;i++)
{fin>>x>>y;
nod *c;
c=new nod;
c->inf=y;
c->urm=l[x];
l[x]=c;
c=new nod;
c->inf=x;
c->urm=a[y];
a[y]=c;
}
}
void dfs(int x)
{viz[x]=1;
for(nod *c=l[x];c!=NULL ;c=c->urm)
if(viz[c->inf]==0)
dfs(c->inf);
postordine[++nr]=x;
}
void dfst(int x)
{viz[x]=0;
comp[x]=numar;
for(nod *c=a[x];c!=NULL ;c=c->urm)
if(viz[c->inf]==1)
dfst(c->inf);
}
int main()
{int i,j;
citire();
for(i=1;i<=n;i++)
if(viz[i]==0) dfs(i);
for(i=n;i>=1;i--)
if(viz[postordine[i]])
{dfst(postordine[i]);
numar++;
}
fout<<numar-1<<'\n';
for(j=1;j<=numar;j++)
{for(i=1;i<=n;i++)
if(comp[i]==j)
fout<<i<<' ';
fout<<'\n';
}
fin.close();
fout.close();
return 0;
}