Pagini recente » Cod sursa (job #695369) | Cod sursa (job #2275506) | Cod sursa (job #2228652) | Cod sursa (job #2700218) | Cod sursa (job #1828580)
#include <fstream>
#include <iostream>
#include <stack>
#include <vector>
using namespace std;
ifstream f("ctc.in");
ofstream g("ctc.out");
int n,index,m,i,s,viz[100001],pes[100001],ll[100001];
int fr;
long long nr;
stack <int> S;
vector <int> a[100001],sol[100001];
void tc(int v)
{ viz[v]=index;
ll[v]=index;
index++;
S.push(v);
pes[v]=1;
vector<int> :: iterator it=a[v].begin(), sf=a[v].end();
for(;it!=sf;it++)
{ int j=(*it);
if(!viz[j]) {tc(j);ll[v]=min(ll[v],ll[j]);}
else if(pes[j]) ll[v]=min(ll[v],viz[j]);
}
if(ll[v]==viz[v])
{ if(fr==0 or v!=1)nr++;
int w;
do
{ w=S.top();
S.pop();
pes[w]=0;
sol[nr].push_back(w);
if(w==1) fr++;
}
while(w!=v);
}
}
void tarjan()
{ index=0;
for(i=1;i<=n;i++)
if(!viz[i]) {tc(i);}
}
int main()
{ f>>n>>m;
for(i=1;i<=m;i++)
{ int u,v;
f>>u>>v;
a[u].push_back(v);
}
tarjan();
g<<nr<<'\n';
for(int i=1;i<=nr;i++)
{ vector<int> :: iterator it=sol[i].begin(),sf=sol[i].end();
for(;it!=sf;it++)
{g<<(*it)<<' ';}
g<<'\n';
}
return 0;
}