Pagini recente » Cod sursa (job #592196) | Cod sursa (job #1781572) | Cod sursa (job #2664966) | Cod sursa (job #2142476) | Cod sursa (job #1472168)
#include <cstdio>
#include <bitset>
#define Nmax 100005
#define Bmax 600005
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()
{
scanf("%d%d",&N,&M);
int a,b;
for(int i = 1; i <= M; ++i)
{
scanf("%d%d",&a,&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;
}