Pagini recente » Cod sursa (job #1138967) | Cod sursa (job #2140202) | Cod sursa (job #1760854) | Cod sursa (job #1778242) | Cod sursa (job #355426)
Cod sursa(job #355426)
#include<stdio.h>
#include<vector>
#include<stack>
#include<algorithm>
#include<list>
using namespace std;
#define nMax 100010
int n,m,nrSol,ind;
vector <int> a[nMax];
vector <int> In(nMax,-1),low(nMax),r;
vector < vector <int> > rez;
list <int> st;
void tarjan(int N)
{
In[N]=low[N]=ind++;
st.push_back(N);
for(vector <int> ::iterator it=a[N].begin();it!=a[N].end();it++)
{
if(In[*it]<0)
{
tarjan(*it);
low[N]=min(low[N],low[*it]);
}
else
if(find(st.begin(),st.end(),*it)!=st.end())
{
low[N]=min(low[N],low[*it]);
}
}
if(low[N]==In[N])
{
int x;
r.clear();
do
{
r.push_back(x=st.back());
st.pop_back();
}while(x!=N);
rez.push_back(r);
}
}
int main()
{
freopen("ctc.in","r",stdin);
freopen("ctc.out","w",stdout);
scanf("%d%d",&n,&m);
for(int i=0;i<m;i++)
{
int x,y;
scanf("%d%d",&x,&y);
a[x].push_back(y);
}
for(int i=1;i<=n;i++)
if(In[i]<0)
tarjan(i);
printf("%d\n",rez.size());
for(int i=0;i<rez.size();i++)
{
for(int j=0;j<rez[i].size();j++)
printf("%d ",rez[i][j]);
printf("\n");
}
return 0;
}