Pagini recente » Cod sursa (job #479305) | Cod sursa (job #1651562) | Cod sursa (job #281416) | Cod sursa (job #2124929) | Cod sursa (job #413109)
Cod sursa(job #413109)
#include<iostream>
#include<string>
#include<vector>
using namespace std;
#define NM 100005
vector<int> G[NM],GT[NM],CT[NM];
char viz[NM];
int p[NM],dim,ctc;
void DF(int nod)
{
viz[nod]=1;
for(int i=0;i<G[nod].size();++i)
{
int nnod=G[nod][i];
if(!viz[nnod]) DF(nnod);
}
p[++dim]=nod;
}
void DFT(int nod)
{
viz[nod]=0;
CT[ctc].push_back(nod);
//printf("%d\n",nod);
for(int i=0;i<GT[nod].size();++i)
{
int nnod=GT[nod][i];
if(viz[nnod]) DFT(nnod);
}
}
int main()
{
int N,M,a,b;
freopen("ctc.in","r",stdin);
freopen("ctc.out","w",stdout);
scanf("%d %d",&N,&M);
for(int i=1;i<=M;++i)
{
scanf("%d %d",&a,&b);
G[a].push_back(b);
GT[b].push_back(a);
}
for(int i=1;i<=N;++i)
if(!viz[i]) DF(i);
for(int i=N;i>=1;--i)
if(viz[p[i]])
{
++ctc;
DFT(p[i]);
}
printf("%d\n",ctc);
for(int i=1;i<=ctc;++i)
{
for(int j=0;j<CT[i].size();++j)
printf("%d ",CT[i][j]);
printf("\n");
}
return 0;
}