Pagini recente » Cod sursa (job #2074991) | Cod sursa (job #1749532) | Cod sursa (job #2866357) | Cod sursa (job #616063) | Cod sursa (job #1151859)
#include <iostream>
#include <cstdio>
#include <vector>
#include <stack>
#define Nmax 100010
using namespace std;
vector <int> Graf[Nmax];
vector <int> GrafT[Nmax];
stack <int> S;
int Viz[Nmax];
int NrC;
int N,M;
void Citire()
{
int x,y;
scanf("%d %d",&N,&M);
for(int i=0;i<M;++i)
{
scanf("%d %d",&x,&y);
Graf[x].push_back(y);
GrafT[y].push_back(x);
}
}
void DFS(int V)
{
for(int i=0;i<Graf[V].size();++i)
{
int x=Graf[V][i];
if(!Viz[x])
{
Viz[x]=-1;
DFS(x);
}
}
S.push(V);
}
void DFST(int V)
{
Viz[V]=NrC;
for(int i=0;i<GrafT[V].size();++i)
{
int x=GrafT[V][i];
if(Viz[x]==-1)
DFST(x);
}
}
int main()
{
freopen("ctc.in","r",stdin);
freopen("ctc.out","w",stdout);
Citire();
NrC=1;
for(int i=1;i<=N;++i)
if(!Viz[i])
{
Viz[i]=-1;
DFS(i);
}
while(!S.empty())
{
int V=S.top();
S.pop();
if(Viz[V]==-1)
{
DFST(V);
NrC++;
}
}
printf("%d\n",NrC-1);
bool ok=false;
for(int i=1;i<=NrC;++i)
{
for(int j=1;j<=N;++j)
if(Viz[j]==i)
{
ok=true;
printf("%d ",j);
}
if(ok)
{
ok=false;
printf("\n");
}
}
return 0;
}