Pagini recente » Cod sursa (job #2052524) | Cod sursa (job #1631245) | Cod sursa (job #509950) | Cod sursa (job #202926) | Cod sursa (job #1283294)
#include <fstream>
#include <list>
#include <stack>
#define DIM 100001
using namespace std;
list<int> nod[DIM],sol[DIM];
stack<int> st;
int n,m,x,y,indx[DIM],lowlink[DIM],index,nr;
void tarjan(int k)
{
++index;
indx[k]=index;
lowlink[k]=index;
st.push(k);
for(list<int>::iterator i=nod[k].begin();i!=nod[k].end();++i)
{
if(indx[*i]==0)
{
tarjan(*i);
lowlink[k]=min(lowlink[k],lowlink[*i]);
}
else if(indx[*i]>0)
lowlink[k]=min(lowlink[k],lowlink[*i]);
}
if(lowlink[k]==indx[k])
{
++nr;
int vf;
do
{
vf=st.top();
sol[nr].push_back(vf);
indx[vf]=-1;
st.pop();
}while(vf!=k);
}
}
int main()
{
ifstream f("ctc.in");
ofstream g("ctc.out");
f>>n>>m;
for(int i=1;i<=m;++i)
{
f>>x>>y;
nod[x].push_back(y);
}
for(int i=1;i<=n;++i)
{
if(indx[i]==0)
tarjan(i);
}
g<<nr<<'\n';
for(int i=1;i<=nr;++i)
{
for(list<int>::iterator j=sol[i].begin();j!=sol[i].end();++j)
g<<*j<<" ";
g<<'\n';
}
f.close();
g.close();
return 0;
}