Pagini recente » Cod sursa (job #793687) | Cod sursa (job #1915492) | Cod sursa (job #2288422) | Cod sursa (job #2036891) | Cod sursa (job #961496)
Cod sursa(job #961496)
#include<cstdio>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;
int nr,poz,n,m,i,x1,y11,ap[100009],Q[100009];
queue < int > cc;
vector < int > a,v[100009],h[100009];
vector < vector < int > > ras;
vector < int > ::iterator it;
void dfs(int nod)
{
vector < int > ::iterator it;
ap[nod]=1;
for(it=v[nod].begin();it!=v[nod].end();it++)
if(ap[*it]==0) dfs(*it);
nr++;
Q[nr]=nod;
}
void afis()
{
vector < int > a;
printf("%d\n",ras.size());
for(i=0;i<ras.size();i++)
{
a=ras[i];
sort(a.begin(),a.end());
for(it=a.begin();it!=a.end();it++)
printf("%d ",*it);
printf("\n");
}
}
int main()
{
freopen("ctc.in","r",stdin);
freopen("ctc.out","w",stdout);
scanf("%d",&n);
scanf("%d",&m);
for(i=1;i<=m;i++)
{
scanf("%d",&x1);
scanf("%d",&y11);
v[x1].push_back(y11);
h[y11].push_back(x1);
}
for(i=1;i<=n;i++)
if(ap[i]==0) dfs(i);
for(i=1;i<=n;i++)
ap[i]=0;
poz=nr;
while(1)
{
while(ap[Q[poz]]==1) poz--;
if(poz==0) break;
cc.push(Q[poz]);
a.clear();
ap[Q[poz]]=1;
a.push_back(Q[poz]);
while(!cc.empty())
{
x1=cc.front();
cc.pop();
for(it=h[x1].begin();it!=h[x1].end();it++)
if(ap[*it]==0)
{
ap[*it]=1;
a.push_back(*it);
cc.push(*it);
}
}
ras.push_back(a);
}
afis();
return 0;
}