Pagini recente » Cod sursa (job #266196) | Cod sursa (job #873799) | Cod sursa (job #1895507) | Cod sursa (job #1014916) | Cod sursa (job #398234)
Cod sursa(job #398234)
#include<stdio.h>
#include<stack>
#include<vector>
#define Nmax 100010
using namespace std;
int n,m,i,ctc,lowlink[Nmax],viz[Nmax],x,y,Index[Nmax],idx,j;
vector <int> G[Nmax],Sol[Nmax];
stack <int> S;
void tarjan (int nod)
{
viz[nod]=1;
Index[nod]=idx;
lowlink[nod]=idx;
++idx;
S.push(nod);
int N=G[nod].size(),i,fiu;
for(i=0;i<N;i++)
{
fiu=G[nod][i];
if(!Index[fiu])
{
tarjan(fiu);
if(lowlink[nod] > lowlink[fiu]) lowlink[nod]=lowlink[fiu];
}
else
if(viz[fiu])
if(lowlink[nod] > lowlink[fiu]) lowlink[nod]=lowlink[fiu];
}
if(Index[nod]==lowlink[nod])
{
ctc++;
do
{
N=S.top();
Sol[ctc].push_back(N);
viz[N]=0;
S.pop();
}
while(N!=nod);
}
}
int main()
{
freopen("ctc.in","r",stdin);
freopen("ctc.out","w",stdout);
scanf("%d %d",&n,&m);
for(i=1;i<=m;i++)
{
scanf("%d %d",&x,&y);
G[x].push_back(y);
}
idx=1;
for(i=1;i<=n;i++)
if(!Index[i]) tarjan(i);
printf("%d\n",ctc);
for(i=1;i<=ctc;i++)
{
m=Sol[i].size();
for(j=0;j<m;j++)
printf("%d ",Sol[i][j]);
printf("\n");
}
return 0;
}