Pagini recente » Cod sursa (job #2306871) | Cod sursa (job #2255936) | Cod sursa (job #2640748) | Cod sursa (job #2419196) | Cod sursa (job #1724461)
#include <fstream>
#include <cstring>
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
int n,m,i,x,y;
struct celula{
int nod;
celula *next;
};
typedef celula *lista;
lista g[100001],gt[100001],a,sol[100001];
int st[100001],vf,viz[100001];
int nrs;
void dfs(int i)
{
viz[i]=1;
for(lista p=g[i]; p; p=p->next)
{
if(viz[p->nod]==0) dfs(p->nod);
}
st[++vf]=i;
}
void dfs2(int i)
{
viz[i]=1;
for(lista p=gt[i]; p; p=p->next )
{
if(viz[p->nod]==0) dfs2(p->nod);
}
a= new celula;
a->nod=i;
a->next=sol[nrs];
sol[nrs]=a;
}
int main()
{
fin>>n>>m;
for(i=1;i<=m;++i)
{
fin>>x>>y;
a=new celula;
a->nod=y;
a->next=g[x];
g[x]=a;
a=new celula;
a->nod=x;
a->next=gt[y];
gt[y]=a;
}
for(i=1;i<=n;++i)
{
if(viz[i]==0) dfs(i);
}
memset(viz,0,sizeof(viz));
for(i=vf;i>=1;--i)
{
if(viz[st[i]]==0) ++nrs, dfs2(st[i]);
}
fout<<nrs<<"\n";
for(i=1;i<=nrs;++i,fout<<"\n")
{
for(lista p=sol[i];p; p=p->next)
fout<<p->nod<<" ";
}
return 0;
}