Pagini recente » Cod sursa (job #3236117) | Cod sursa (job #432097) | Cod sursa (job #2947353) | Cod sursa (job #1450069) | Cod sursa (job #409468)
Cod sursa(job #409468)
#include<stdio.h>
#include<algorithm>
#include<vector>
using namespace std;
vector <int> gp[100002],gm[100002],g[100002];
int n,m,i;
vector <int> tr;
vector <int> viz,d;
void read()
{ int q,w;
scanf("%d%d",&n,&m);
for(i=1;i<=m;i++)
{ scanf("%d%d",&q,&w);
gp[q].push_back(w);
gm[w].push_back(q);
}
}
void dfplus(int nod)
{ viz[nod]=1;
for(vector <int>::iterator it=gp[nod].begin();it!=gp[nod].end();it++)
if(viz[*it]==0)
dfplus(*it);
d.push_back(nod);
}
void dfminus(int nod,int nr)
{ tr[nod]=nr;
for(vector<int>::iterator it=gm[nod].begin();it!=gm[nod].end();it++)
if(tr[*it]==0)
dfminus(*it,nr);
}
int main()
{ freopen("ctc.in","r",stdin);
freopen("ctc.out","w",stdout);
read();
viz.resize(n+1);
for(i=1;i<=n;i++)
if(viz[i]==0)
dfplus(i);
int nr=1;
tr.resize(n+1);
while(d.size()!=0)
{ if(tr[d.back()]==0)
{dfminus(d.back(),nr);
nr++;
}
d.pop_back();
}
for(i=1;i<=n;i++)
g[tr[i]].push_back(i);
nr--;
printf("%d\n",nr);
for(i=1;i<=nr;i++)
{ for(vector<int>::iterator it=g[i].begin();it!=g[i].end();it++)
printf("%d ",*it);
printf("\n");
}
return 0;
}