Pagini recente » Cod sursa (job #2949814) | Cod sursa (job #2162879) | Cod sursa (job #2356959) | Cod sursa (job #411170) | Cod sursa (job #1472140)
#include <cstdio>
#include <bitset>
#define Nmax 100005
#define Bmax 400005
using namespace std;
int G[Nmax],Stak[Nmax],Gt[Nmax],CTC[Nmax];
int Buff[Bmax],pozBuff[Bmax],Next[Bmax],NextT[Bmax],NextC[Bmax];
bitset<Nmax> used;
int DIM,vf,nctc;
void Add_Edge(int x,int y)
{
Buff[++DIM] = y;
Next[DIM] = G[x];
G[x] = DIM;
pozBuff[y] = DIM;
Buff[++DIM] = x;
NextT[DIM] = Gt[y];
Gt[y] = DIM;
pozBuff[x] = DIM;
}
int N,M;
void Read()
{
scanf("%d%d",&N,&M);
int a,b;
for(int i = 1; i <= M; ++i)
{
scanf("%d%d",&a,&b);
Add_Edge(a,b);
}
}
void DFS(int k)
{
used[k] = 1;
for(int v = G[k]; v; v = Next[v])
if(!used[Buff[v]])
DFS(Buff[v]);
Stak[++vf] = k;
}
void DFST(int k)
{
NextC[ pozBuff[k] ] = CTC[nctc];
CTC[ nctc ] = pozBuff[k];
used[k] = 1;
for(int v = Gt[k]; v; v = NextT[v])
if(!used[Buff[v]])
DFST(Buff[v]);
}
void Kosaraju()
{
for(int i = 1; i <= N; ++i)
if(!used[i])
DFS(i);
used = 0;
while(vf > 0)
{
while(vf > 0 && used[ Stak[vf] ])
--vf;
if(vf == 0)
continue;
++nctc;
DFST(Stak[vf]);
}
}
void Print()
{
printf("%d\n",nctc);
for(int i = 1; i <= nctc; ++i)
{
for(int v = CTC[i]; v; v = NextC[ v ])
printf("%d ",Buff[v]);
printf("\n");
}
}
int main()
{
freopen("ctc.in","r",stdin);
freopen("ctc.out","w",stdout);
Read();
Kosaraju();
Print();
return 0;
}