Pagini recente » Cod sursa (job #1339130) | Cod sursa (job #2789489) | Cod sursa (job #1966097) | Cod sursa (job #2391218) | Cod sursa (job #1428392)
#include <cstdio>
#include <vector>
#include <stack>
#include <iterator>
#include <algorithm>
using namespace std;
#define MAXN 100005
vector <int> a[MAXN],id(MAXN,-1),lo(MAXN),in(MAXN,0);
vector <int> r[MAXN];
stack <int> s;
int k=0,h=0;
void tarjan(int x)
{
id[x]=k;
lo[x]=k;
k++;
s.push(x);
in[x]=1;
vector <int>::const_iterator it;
for(it=a[x].begin();it!=a[x].end();++it)
{
if(id[*it]==-1)
{
tarjan(*it);
lo[x]=min(lo[x],lo[*it]);
}
else if (in[*it])
lo[x]=min(lo[x],lo[*it]);
}
if(id[x]==lo[x])
{
int e;
do{
e=s.top();
r[h].push_back(e);
s.pop();
in[e]=0;
}while(e!=x);
h++;
}
}
int main ()
{
int n,m,i,j,x,y;
freopen("ctc.in","r",stdin);
freopen("ctc.out","w",stdout);
scanf("%d%d",&n,&m);
for(i=0;i<m;++i)
{
scanf("%d%d",&x,&y);
a[x-1].push_back(y-1);
}
for(i=0;i<n;i++)
if(id[i]==-1)
tarjan(i);
printf("%d\n",h);
for(i=0;i<h;++i)
{
for(j=0;j<r[i].size();++j)
printf("%d ",r[i][j]+1);
printf("\n");
}
return 0;
}