Pagini recente » Cod sursa (job #1606752) | Cod sursa (job #2622780) | Cod sursa (job #2805092) | Cod sursa (job #2827958) | Cod sursa (job #1232206)
#include<cstdio>
#include<vector>
using namespace std;
vector<int> gno[200005],gin[200005];
int ord[200005],t,ncc,lu[200005],rez[200005],lt;
bool vi[200005];
struct sp
{
int t,n;
}v[100005];
void viz(int nod)
{
int j;
for(j=gno[nod].size()-1;j>=0;j--)
if(vi[gno[nod][j]]==0)
{
vi[gno[nod][j]]=1;
viz(gno[nod][j]);
}
ord[++t]=nod;
}
void ctc(int nod)
{
int j;
lu[ncc]++;
lt++;
rez[lt]=nod;
for(j=gin[nod].size()-1;j>=0;j--)
if(vi[gin[nod][j]]==0)
{
vi[gin[nod][j]]=1;
ctc(gin[nod][j]);
}
}
int main()
{
freopen("ctc.in","r",stdin);
freopen("ctc.out","w",stdout);
int n,m,i,x,y,j;
scanf("%d%d",&n,&m);
for(i=1;i<=m;i++)
{
scanf("%d%d",&x,&y);
gno[x].push_back(y);
gin[y].push_back(x);
}
t=0;
for(i=1;i<=n;i++)
if(vi[i]==0)
{
vi[i]=1;
viz(i);
}
for(i=1;i<=n;i++)
vi[i]=0;
ncc=lt=0;
for(i=t;i>=1;i--)
if(vi[ord[i]]==0)
{
ncc++;
ctc(ord[i]);
}
j=0;
printf("%d\n",ncc);
for(i=1;i<=ncc;i++)
{
x=j+lu[i]-1;
for(j=j+1;j<=x;j++)
printf("%d ",rez[j]);
printf("\n");
}
return 0;
}