Pagini recente » Cod sursa (job #1830727) | Cod sursa (job #2177057) | Cod sursa (job #2857793) | Cod sursa (job #2181078) | Cod sursa (job #1538116)
#include<cstdio>
#include<vector>
using namespace std;
vector<int> v[100001],v1[100001],r[100001];
int n,m,i,j,k,l,st[100001],cate,vc[100001],cate1,cate2,vc1[100001];
void dfs(int nod)
{
vc[nod]=1;
for(int co=0;co<v[nod].size();co++)
if(vc[v[nod][co]]==0)
dfs(v[nod][co]);
st[++cate]=nod;
}
void dfs1(int nod)
{
if(vc[nod]==1)
r[cate1].push_back(nod);
vc1[nod]=1;
for(int co=0;co<v1[nod].size();co++)
if(vc1[v1[nod][co]]==0)
dfs1(v1[nod][co]);
}
int main ()
{
freopen("ctc.in","r",stdin);
freopen("ctc.out","w",stdout);
scanf("%d%d",&n,&m);
for(i=1;i<=m;i++)
{
int x,y;
scanf("%d%d",&x,&y);
v[x].push_back(y);
v1[y].push_back(x);
}
for(i=1;i<=n;i++)
if(vc[i]==0)
{
cate=0;
dfs(i);
for(j=cate;j>=1;j--)
if(vc1[st[j]]==0)
{
cate1++;
dfs1(st[j]);
if(r[cate1].size()==0)
cate1--;
}
}
printf("%d\n",cate1);
for(i=1;i<=cate1;i++)
{
for(j=0;j<r[i].size();j++)
printf("%d ",r[i][j]);
printf("\n");
}
return 0;
}