Pagini recente » Cod sursa (job #2064159) | Cod sursa (job #2790892) | Cod sursa (job #1778472) | Cod sursa (job #2396753) | Cod sursa (job #963951)
Cod sursa(job #963951)
#include<stdio.h>
#include<vector>
#include<stack>
#include<stdlib.h>
using namespace std;
int n,m;
vector <int> graf[100001],suc,pred,graf2[100001],ctc[1000];
int viz[100001];
void read()
{
int x,y,i;
scanf("%d %d",&n,&m);
for (i=1;i<=m;++i)
{ scanf("%d %d",&x,&y); graf[x].push_back(y);}
}
void transpunere()
{
int x,y,i,j;
for (i=1;i<=n;++i)
for (j=0;j<graf[i].size();++j)
{ graf2[graf[i][j]].push_back(i);}
}
int num;
void dfs1(int nod)
{
int i;
viz[nod]=1;
int l=graf[nod].size();
for (i=0;i<l;++i)
if (!viz[graf[nod][i]]) dfs1(graf[nod][i]);
suc.push_back(nod);
}
void dfs2(int nod)
{
int i;
viz[nod]=1;
int l=graf2[nod].size();
for (i=0;i<l;++i)
if (!viz[graf2[nod][i]]) dfs2(graf2[nod][i]);
ctc[num].push_back(nod);
}
/*void solve()
{
int i,j;
int l=suc.size();
for (i=l-1;i>=0;--i)
}*/
void write()
{
printf("%d\n",num);
for ( int i=1;i<=num;++i)
{for (int j=0;j<=ctc[i].size()-1;++j)
printf("%d ",ctc[i][j]); printf("\n"); }
}
void setviz()
{
memset(viz,0,sizeof(viz));
}
int main ()
{
freopen("ctc.in","r",stdin);
freopen("ctc.out","w",stdout);
read();
int i;
for (i=1;i<=n;++i)
if (!viz[i])
dfs1(i);
transpunere();
setviz();
int l=suc.size();
for (i=l-1;i>=0;--i)
if (!viz[suc[i]])
{num++;dfs2(suc[i]);}
//solve();
write();
}