Pagini recente » Cod sursa (job #2940882) | Cod sursa (job #730487) | Cod sursa (job #1604573) | Cod sursa (job #352188) | Cod sursa (job #467567)
Cod sursa(job #467567)
#include<stdio.h>
#include<stdlib.h>
#define dim 100009
using namespace std;
int n,m,i,k,x,y,j;
char viz[dim];
int ord[dim],*a[dim],*at[dim],*mat[dim];
void dfs(int nod)
{int i;
viz[nod]=1;
for(i=1;i<=a[nod][0];i++)
if(!viz[a[nod][i]])
dfs(a[nod][i]);
k++;
ord[k]=nod;}
void dfst(int nod)
{int i;
viz[nod]=0;
mat[k][0]++;
mat[k]=(int *)realloc(mat[k], (mat[k][0]+1)*sizeof(int));
mat[k][mat[k][0]]=nod;
for(i=1;i<=at[nod][0];i++)
if(viz[at[nod][i]])
dfst(at[nod][i]);
}
int main()
{
FILE *f=fopen("ctc.in","r"), *g=fopen("ctc.out","w");
fscanf(f,"%d%d",&n,&m);
for(i=1;i<=n;i++)
{a[i]=(int *)realloc(a[i],sizeof(int));
a[i][0]=0;
at[i]=(int *)realloc(at[i],sizeof(int));
at[i][0]=0;
}
for(i=1;i<=m;i++)
{fscanf(f,"%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;
at[y][0]++;
at[y]=(int *)realloc(at[y], (at[y][0]+1)*sizeof(int));
at[y][at[y][0]]=x;
}
for(i=1;i<=n;i++)
if(!viz[i])
dfs(i);
k=-1;
for(i=n;i>=1;i--)
if(viz[ord[i]])
{k++; mat[k]=(int *)realloc(mat[k],sizeof(int)); mat[k][0]=1;
dfst(ord[i]);
}
fprintf(g,"%d\n",k+1);
for(i=0;i<=k;i++)
{for(j=2;j<=mat[i][0];j++)
fprintf(g,"%d ",mat[i][j]);
fprintf(g,"\n");}
fclose(f);
fclose(g);
return 0;
}