Pagini recente » Cod sursa (job #2690567) | Cod sursa (job #1117191) | Cod sursa (job #348605) | Cod sursa (job #2664695) | Cod sursa (job #529493)
Cod sursa(job #529493)
#include<cstdio>
#include<vector>
using namespace std;
const int N=100005;
int ctc,q,n,m,v[N],poz[N];
bool f[N];
vector<int> L[N],LT[N],rez[N];
void read()
{
int x,y;
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",&x,&y);
L[x].push_back(y);
LT[y].push_back(x);
}
}
void makevec(int nod)
{
f[nod]=true;
for(vector<int>::iterator it=L[nod].begin();it!=L[nod].end();it++)
if(!f[*it])
makevec(*it);
v[++q]=nod;
poz[nod]=q;
}
void init()
{
for(int i=1;i<=n;i++)
if(!f[i])
makevec(i);
}
void reset(bool f[N])
{
for(int i=1;i<=n;i++)
f[i]=false;
}
void dfs(int nod)
{
f[poz[nod]]=true;
for(vector<int>::iterator it=LT[nod].begin();it!=LT[nod].end();it++)
if(!f[poz[*it]])
dfs(*it);
rez[ctc].push_back(nod);
}
void solve()
{
for(int i=n;i>=1;i--)
if(!f[i])
{
ctc++;
dfs(v[i]);
}
}
void afis()
{
printf("%d\n",ctc);
for(int i=1;i<=ctc;i++)
{
for(vector<int>::iterator it=rez[i].begin();it!=rez[i].end();it++)
printf("%d ",*it);
printf("\n");
}
}
int main()
{
read();
init();
reset(f);
solve();
afis();
return 0;
}