Pagini recente » Cod sursa (job #779850) | Cod sursa (job #2458728) | Cod sursa (job #1835136) | Cod sursa (job #2433428) | Cod sursa (job #497046)
Cod sursa(job #497046)
#include<stdio.h>
#include<vector>
#define N 100010
using namespace std;
vector<int> v[N],C[N],stiva;
int n,m,i,a,b,viz[N],low[N],dsfnum[N],top,num,nc;
void read(),solve(),visit(int);
int main()
{
read();
solve();
return 0;
}
void read()
{
freopen("ctc.in","rt",stdin);
freopen("ctc.out","wt",stdout);
scanf("%d%d",&n,&m);
for(i=1;i<=m;i++)
{
scanf("%d%d",&a,&b);
v[a].push_back(b);
}
}
void solve()
{
vector<int>::iterator it;
for(i=1;i<=n;i++)
if(!viz[i])
{
num=0;
visit(i);
}
printf("%d",nc);
for(i=1;i<=nc;i++)
{
printf("\n");
for(it=C[i].begin();it!=C[i].end();it++)
printf("%d ",*it);
}
printf("\n");
}
void visit(int p)
{
int nod;
vector<int>::iterator it;
viz[p]=1;
stiva.push_back(p);//add p to L
dsfnum[p]=++num;//increment N
low[p]=dsfnum[p];
for(it=v[p].begin();it!=v[p].end();it++)
{
if(viz[*it]==2)continue;
if(!viz[*it]) visit(*it);
low[p]=(low[p]<low[*it])?low[p]:low[*it];
}
if(low[p]==dsfnum[p])
{
nc++;
for(;;)
{
nod=stiva.back();
viz[nod]=2;
C[nc].push_back(nod);
stiva.pop_back();
if(nod==p)break;
}
}
}