Pagini recente » Cod sursa (job #771078) | Cod sursa (job #949788) | Cod sursa (job #671416) | Cod sursa (job #440257) | Cod sursa (job #2197432)
#include <fstream>
#include <bitset>
using namespace std;
ifstream cin("ctc.in");
ofstream cout("ctc.out");
bitset <100005> ap;
int n,m,vf,nr;
struct nod{
int val;
nod *next;
};
int varf[100005];
nod *lista[100005],*nonlista[100005],*sol[100005];
void add(int x, int y)
{
nod *e=new nod;
e->val=x;
e->next=lista[y];
lista[y]=e;
nod *a=new nod;
a->val=y;
a->next=nonlista[x];
nonlista[x]=a;
}
void ADD(int x, int y)
{
nod *e=new nod;
e->val=x;
e->next=sol[y];
sol[y]=e;
}
void ndfs(int x)
{
ap[x]=1;
nod *e=lista[x];
while(e)
{
if(!ap[e->val])
{
ndfs(e->val);
}
e=e->next;
}
vf++;
varf[vf]=x;
}
void dfs(int x)
{
ap[x]=0;
nod *e=nonlista[x];
while(e)
{
if(ap[e->val])
{
dfs(e->val);
}
e=e->next;
}
ADD(x,nr);
}
int main()
{
cin >> n >> m;
for(int i=1; i<=m; i++)
{
int x,y;
cin >> x >> y;
add(x,y);
}
for(int i=1; i<=n; i++)
{
if(!ap[i])
ndfs(i);
}
for(int i=vf; i>=1; i--)
{
if(ap[varf[i]])
{
nr++;
dfs(varf[i]);
}
}
cout << nr << '\n';
for(int i=1; i<=nr; i++)
{
while(sol[i])
{
cout << sol[i]->val << ' ';
sol[i]=sol[i]->next;
}
cout << '\n';
}
return 0;
}