Pagini recente » Cod sursa (job #1882681) | Cod sursa (job #1026975) | Cod sursa (job #3238555) | Cod sursa (job #474322) | Cod sursa (job #1357126)
#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;
vector <int> g1[100010];
vector <int> g2[100010];
vector <int> postordine;
vector <int> sol[100010];
int m,n,s;
void citire()
{
freopen("ctc.in","r",stdin);
scanf("%d %d",&n,&m);
for(int i=0;i<m;i++)
{
int a,b;
scanf("%d %d",&a,&b);
g1[a].push_back(b);
g2[b].push_back(a);
}
}
int viz[100010];
int vizctc[100010];
void DFS(int k)
{
for(int i=0;i<g1[k].size();i++)
{
if(!viz[g1[k][i]])
{
viz[g1[k][i]]=1;
DFS(g1[k][i]);
}
}
postordine.push_back(k);
}
void DFSctc(int k)
{
sol[s].push_back(k);
for(int i=0;i<g2[k].size();i++)
{
if(!vizctc[g2[k][i]])
{
vizctc[g2[k][i]]=1;
DFSctc(g2[k][i]);
}
}
}
void ctc()
{
for(int i=1;i<=n;i++)
if(!viz[i])
{
viz[i]=1;
DFS(i);
}
for(int i=postordine.size()-1;i>=0;i--)
if(!vizctc[postordine[i]])
{
s++;
vizctc[postordine[i]]=1;
DFSctc(postordine[i]);
}
}
void afisare()
{
freopen("ctc.out","w",stdout);
printf("%d\n",s);
for(int i=1;i<=s;i++)
{
for(int j=0;j<sol[i].size();j++)
printf("%d ",sol[i][j]);
printf("\n");
}
}
int main()
{
citire();
ctc();
afisare();
return 0;
}