Pagini recente » Cod sursa (job #1834918) | Cod sursa (job #1288391) | Cod sursa (job #1392068) | Cod sursa (job #2084614) | Cod sursa (job #1472175)
#include <cstdio>
#include <bitset>
#define Nmax 100005
#define Bmax 500005
#define BU 3666013
char Baff[BU];
int pz = BU - 1;
void Read(int &A){
A = 0;
while('0' > Baff[pz] || Baff[pz] > '9')
if(++pz == BU)
fread(Baff,1,BU,stdin),pz = 0;
while('0' <= Baff[pz] && Baff[pz] <= '9')
{
A = (A<<3) + (A<<1) + Baff[pz] - 48;
if(++pz == BU)
fread(Baff,1,BU,stdin),pz = 0;
}
}
using namespace std;
int G[Nmax],Gt[Nmax],CTC[Nmax],Stak[Nmax];
bitset<Nmax> used;
int DIM,vf,nctc;
class node{
public:
int inf,next;
node(){}
node(int elem,int to){
inf = elem;
next = to;
}
};
node Buff[Bmax];
void Add_list(int &head,int val){
Buff[++DIM] = node(val,head);
head = DIM;
}
int N,M;
void Read()
{
Read(N);Read(M);
int a,b;
for(int i = 1; i <= M; ++i)
{
Read(a);Read(b);
Add_list(G[a],b);
Add_list(Gt[b],a);
}
}
void DFS(int k)
{
used[k] = 1;
for(int v = G[k]; v; v = Buff[v].next)
if(!used[Buff[v].inf])
DFS(Buff[v].inf);
Stak[++vf] = k;
}
void DFST(int k)
{
Add_list(CTC[nctc],k);
used[k] = 1;
for(int v = Gt[k]; v; v = Buff[v].next)
if(!used[Buff[v].inf])
DFST(Buff[v].inf);
}
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 = Buff[v].next)
printf("%d ",Buff[v].inf);
printf("\n");
}
}
int main()
{
freopen("ctc.in","r",stdin);
freopen("ctc.out","w",stdout);
Read();
Kosaraju();
Print();
return 0;
}