Pagini recente » Cod sursa (job #2595346) | Cod sursa (job #2222854) | Cod sursa (job #2310263) | Cod sursa (job #1672066) | Cod sursa (job #539255)
Cod sursa(job #539255)
#include <stdio.h>
#include <stdlib.h>
using namespace std;
#define MaxN 100005
#define min(a,b) (a<b ? a:b)
int vf_index[MaxN],low[MaxN],in_stiva[MaxN],s[MaxN];
int *comp[MaxN],*a[MaxN];
int n,index,nrcomp,nrvf;
void citire(void)
{ FILE *fin=fopen("ctc.in","r");
int m,x,y;
fscanf(fin,"%d%d",&n,&m);
for(int k=1;k<=n;k++)
{ a[k]=(int*)realloc(a[k],sizeof(int));
a[k][0]=0;
}
for(;m;m--)
{ fscanf(fin,"%d%d",&x,&y);
a[x][0]++;
a[x]=(int*)realloc(a[x],(a[x][0]+1)*sizeof(int));
a[x][a[x][0]]=y;
}
fclose(fin);
}
void componente(int u)
{ int v;
vf_index[u]=low[u]=++index;
s[nrvf++]=u; in_stiva[u]=1;
for(int i=1;i<=a[u][0];i++)
{ v=a[u][i];
if(!vf_index[v])
{ componente(v);
low[u]=min(low[u],low[v]);
}
else
if(in_stiva[v]) low[u]=min(low[u],vf_index[v]);
}
if(vf_index[u]==low[u])
{ nrcomp++;
comp[nrcomp]=(int*)realloc(comp[nrcomp],sizeof(int));
comp[nrcomp][0]=0;
do
{ v=s[--nrvf]; in_stiva[v]=0;
comp[nrcomp][0]++;
comp[nrcomp]=(int*)realloc(comp[nrcomp],(comp[nrcomp][0]+1)*sizeof(int));
comp[nrcomp][comp[nrcomp][0]]=v;
}while (v!=u);
}
}
void tarjan(void)
{ index=nrvf=nrcomp=0;
for(int k=1;k<=n;k++)
if(!vf_index[k]) componente(k);
}
void scrie(void)
{ FILE *fout=fopen("ctc.out","w");
fprintf(fout,"%d\n",nrcomp);
for(int k=1;k<=nrcomp;k++)
{ for(int i=comp[k][0];i>0;i--)
fprintf(fout,"%d ",comp[k][i]);
fprintf(fout,"\n");
}
fclose(fout);
}
int main(void)
{ citire();
tarjan();
scrie();
return 0;
}