Pagini recente » Cod sursa (job #910849) | Cod sursa (job #395845) | Profil Mr. Teofilos | Cod sursa (job #1526664) | Cod sursa (job #1039097)
#include <cstdio>
#include <vector>
#define nmax 100010
using namespace std;
vector<int> g[nmax],gt[nmax],post,ctc[nmax];
int n,m,viz[nmax],nr;
void DFS(int vf)
{
viz[vf]=1;
vector<int>::iterator it;
for(it=g[vf].begin();it!=g[vf].end();it++)
if(!viz[*it])
DFS(*it);
post.push_back(vf);
}
void citire()
{
scanf("%d%d",&n,&m);
int i,x,y;
for(i=1;i<=m;i++)
{
scanf("%d%d",&x,&y);
g[x].push_back(y);
gt[y].push_back(x);
}
}
void DFST(int vf)
{
viz[vf]=0;
ctc[nr].push_back(vf);
vector<int>::iterator it;
for(it=gt[vf].begin();it!=gt[vf].end();it++)
if(viz[*it])
DFST(*it);
}
void afisare()
{
printf("%d\n",nr);
int i,j;
for(i=0;i<=nr;i++)
{
for(j=0;j<ctc[i].size();j++)
printf("%d ",ctc[i][j]);
printf("\n");
}
}
int main()
{
freopen("ctc.in","r",stdin);
freopen("ctc.out","w",stdout);
citire();
int i;
for(i=1;i<=n;i++)
if(!viz[i])
DFS(i);
for(i=post.size()-1;i>=0;i--)
if(viz[post[i]])
{
DFST(post[i]);
nr++;
}
afisare();
return 0;
}