Pagini recente » Cod sursa (job #31045) | Cod sursa (job #61871) | Cod sursa (job #3252318) | Cod sursa (job #504546)
Cod sursa(job #504546)
#include <stdio.h>
#include <stdlib.h>
#define NMAX 50001
FILE * fin = fopen("retele.in","r");
FILE * fout = fopen("retele.out","w");
int n,nr,nrc;
int * A[NMAX], * AT[NMAX], *c[NMAX];
int postordine[NMAX], viz[NMAX];
void citire(){
int x,y,m,i;
fscanf(fin,"%d %d",&n,&m);
for(i=1;i<=n;i++){
c[i] = (int *)realloc(c[i],sizeof(int));
c[i][0] = 0;
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(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;
AT[y][0]++;
AT[y] = (int *)realloc(AT[y], (AT[y][0]+1)*sizeof(int));
AT[y][AT[y][0]]=x;
}
}
void dfs(int x){
int i;
viz[x] = 1;
for(i=1;i<=A[x][0];++i)
if(!viz[A[x][i]])
dfs(A[x][i]);
postordine[++nr] = x;
}
void dfst(int x){
int i;
viz[x] = 0;
//printf(" %d",x);
c[nrc][0]++;
c[nrc] = (int *)realloc(c[nrc],(c[nrc][0]+1)*sizeof(int));
c[nrc][c[nrc][0]] = x;
for(i=1;i<=AT[x][0];++i)
if(viz[AT[x][i]])
dfst(AT[x][i]);
}
void afisare(){
int i,j;
fprintf(fout,"%d\n", nrc);
for(i=1;i<=nrc;i++){
fprintf(fout,"%d\n",c[i][0]);
for(j=1;j<=c[i][0];j++)
fprintf(fout,"%d ",c[i][j]);
fprintf(fout,"\n");
}
}
int main(){
int i;
citire();
for(i=1;i<=n;++i)
if(!viz[i]) dfs(i);
for(i=n;i>0;--i)
if(viz[postordine[i]]){
//printf("componenta tare conexa %d", ++nrc);
nrc++;
dfst(postordine[i]);
printf("\n");
}
afisare();
return 0;
}