Pagini recente » Cod sursa (job #768732) | Cod sursa (job #2840116) | Cod sursa (job #259832) | Cod sursa (job #2794387) | Cod sursa (job #1491528)
#include <vector>
#include <stack>
#include <cstdio>
#define min(a,b) ( (a)<(b)? (a) : (b) )
using namespace std;
int n,m,idx[100010],lowlink[100010],in_stack[100010],index;
vector <int> vert[100010],ctc;
stack <int> s;
vector< vector<int> > sol;
int minim(int a,int b)
{
if(a<b) return a;
else return b;
}
void tarjan(int v)
{
index++;
idx[v]=index; lowlink[v]=index;
s.push(v); in_stack[v]=1;
vector<int>::const_iterator it;
for(it=vert[v].begin();it!=vert[v].end();it++)
if(idx[*it]==0) { tarjan(*it); lowlink[v]=minim(lowlink[v],lowlink[*it]); }
else if(in_stack[*it]) lowlink[v]=minim(lowlink[v],lowlink[*it]);
if(lowlink[v]==idx[v])
{
ctc.clear();
int node;
do
{
ctc.push_back(node=s.top()); s.pop(); in_stack[node]=0;
}while(node!=v);
sol.push_back(ctc);
}
}
int main()
{
int n1,n2,j;
freopen("ctc.in","r",stdin);
freopen("ctc.out","w",stdout);
scanf("%d%d",&n,&m);
for(;m;m--)
{
scanf("%d%d",&n1,&n2);
vert[n1].push_back(n2);
}
for(int i2=1;i2<=n;i2++)
if(idx[i2]==0) tarjan(i2);
printf("%d\n",sol.size());
for(int i=0;i<sol.size();i++)
{
for(j=0;j<sol[i].size();j++) printf("%d ",sol[i][j]);
printf("\n");
}
fclose(stdin);
fclose(stdout);
return 0;
}