Pagini recente » Cod sursa (job #71541) | Cod sursa (job #1589802) | Cod sursa (job #1416746) | Cod sursa (job #1484730) | Cod sursa (job #2333920)
#include <fstream>
using namespace std;
ifstream f("ctc.in");
ofstream g("ctc.out");
struct nod{
int inf;
nod *urm;
}*l[100005],*sol[100005];
int y,i,x,n,m, nrctc,lowlink[100005],index,viz[100005],k,st[100005],idx[100005];
void adaug(nod *&v,int x){
nod *p;
p=new nod;
p->inf=x;
p->urm=v;
v=p;
}
void tarjan(int x){
st[++k]=x;viz[x]=1;
idx[x]=lowlink[x]=++index;
for(nod *p=l[x];p;p=p->urm){
int y=p->inf;
if(!idx[y]){
tarjan(y);
lowlink[x]=min(lowlink[x],lowlink[y]);
}
else if(viz[y]) { lowlink[x]=min(lowlink[x],lowlink[y]);
}
}
if(idx[x]==lowlink[x]){nrctc++;
int ww;
do { ww=st[k];
k--;
viz[ww]=0;
adaug(sol[nrctc],ww);
}while(ww!=x);
}
}
int main()
{
f>>n>>m;
for(i=1;i<=m;i++){
f>>x>>y;
adaug(l[x],y);
}
for(i=1;i<=n;i++)
if(!idx[i])tarjan(i);
g<<nrctc<<'\n';
for(i=1;i<=nrctc;i++){
for(nod *j=sol[i];j;j=j->urm) g<<j->inf<<" ";
g<<'\n';
}
return 0;
}