Pagini recente » Cod sursa (job #1810512) | Cod sursa (job #2663871) | Cod sursa (job #342725) | Cod sursa (job #2055202) | Cod sursa (job #799871)
Cod sursa(job #799871)
#include<stdio.h>
#define dim 100010
int viz[dim],low[dim],next,i,j,n,m,nr,a,b,stiva[dim],R[10][dim];
FILE*f=fopen("ctc.in","r");
FILE*g=fopen("ctc.out","w");
struct nod{
int nr;
nod *adr;
}*p,*L[dim];
void read(){
fscanf(f,"%d%d",&n,&m);
for(i=1;i<=m;i++){
fscanf(f,"%d%d",&a,&b);
p=new nod;
p->nr=b;
p->adr=L[a];
L[a]=p;
}
}
int min(int a,int b){
if(a<b)
return a;
return b;
}
void dfs(int x){
next++;
viz[x]=next;
low[x]=next;
stiva[++stiva[0]]=x;
nod *c;
for(c=L[x];c!=0;c=c->adr){
if(!viz[c->nr]){
dfs(c->nr);
low[x]=min(low[x],low[c->nr]);
}
else{
if(viz[c->nr]>0)
low[x]=min(low[x],low[c->nr]);
}
}
if(viz[x]==low[x]){
nr++;
do{
R[nr][++R[nr][0]]=stiva[stiva[0]];
viz[stiva[stiva[0]]]*=(-1);
stiva[0]--;
}while(stiva[stiva[0]]!=x);
R[nr][++R[nr][0]]=stiva[stiva[0]];
stiva[0]--;
}
}
int main(){
read();
for(i=1;i<=n;i++){
if(!viz[i]){
dfs(i);
}
}
fprintf(g,"%d\n",nr);
for(i=1;i<=nr;i++){
for(j=1;j<=R[i][0];j++)
fprintf(g,"%d ",R[i][j]);
fprintf(g,"\n");
}
return 0;
}