Pagini recente » Cod sursa (job #263948) | Cod sursa (job #405494) | Cod sursa (job #2193674) | Cod sursa (job #1908448) | Cod sursa (job #1249738)
#include <fstream>
#define NMAX 100004
using namespace std;
ifstream cin("ctc.in");
ofstream cout("ctc.out");
struct nod{int nr;nod*urm;};
typedef nod*Lista;
Lista lis[NMAX],lisgt[NMAX];
int n,m,post[NMAX],uz[NMAX],np;
void bfs(int);
void dfs(int);
void inserare(Lista&,int);
void solve();
void read();
void write();
int main()
{
read();
solve();
write();
cin.close();cout.close();
return 0;
}
void read()
{
int i,x,y;
cin>>n>>m;
for (i=1;i<=n;i++) {lis[i]=NULL;lisgt[i]=NULL;uz[i]=1;}
for (i=1;i<=m;i++)
{
cin>>x>>y;
inserare(lis[x],y);
inserare(lisgt[y],x);
}
}
void inserare(Lista&prim,int nr)
{
Lista aux;
aux=new nod;
aux->nr=nr;
aux->urm=prim;
prim=aux;
}
int nr;
void solve()
{
int i;
for (i=1;i<=n;i++)
if (uz[i])
dfs(i);
for (i=n;i>=1;i--)
if (!uz[post[i]])
bfs(post[i]);
}
void dfs(int nod)
{
Lista aux=lis[nod];
uz[nod]=0;
while (aux!=NULL)
{
if (uz[aux->nr])
dfs(aux->nr);
aux=aux->urm;
}
post[++np]=nod;
}
int que[NMAX];
void bfs(int nod)
{
Lista aux;int p=1,u=1;
nr++;
que[1]=nod;uz[nod]=nr;
while (p<=u)
{
aux=lisgt[que[p]]; p++;
while (aux!=NULL)
{
if (!uz[aux->nr])
{
uz[aux->nr]=nr;
que[++u]=aux->nr;
}
aux=aux->urm;
}
}
}
void write()
{
int i,j;
cout<<nr<<'\n';
for (i=1;i<=nr;i++){
for (j=1;j<=n;j++)
if (uz[j]==i)
cout<<j<<' ';
cout<<'\n';
}
}