Pagini recente » Cod sursa (job #423704) | Cod sursa (job #832266) | Cod sursa (job #1124304) | Cod sursa (job #1078368) | Cod sursa (job #280480)
Cod sursa(job #280480)
#include <stdio.h>
#include <stdlib.h>
FILE *f=fopen("ctc.in","r"),*g=fopen("ctc.out","w");
#define nmax 100001
int n,nr,nrc;
int *a[nmax],*at[nmax],*componenta[nmax];
int postordine[nmax],viz[nmax];
void citire();
void dfs(int);
void dfst(int);
void afisare();
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]]){
nrc++;
componenta[nrc]=(int*)realloc(componenta[nrc],sizeof(int));
componenta[nrc][0]=0;
dfst(postordine[i]);
}
}
// printf("(%d)",nrc);
afisare();
fclose(f);
fclose(g);
return 0;
}
void citire(){
int m;
fscanf(f,"%d%d",&n,&m);
int x,y,i;
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],sizeof(int)*(a[x][0]+1));
a[x][a[x][0]]=y;
at[y][0]++;
at[y]=(int*)realloc(at[y],sizeof(int)*(at[y][0]+1));
at[y][at[y][0]]=x;
}
}
void dfs(int x){
viz[x]=1;
int i;
for(i=1;i<=a[x][0];i++)
if(!viz[a[x][i]])dfs(a[x][i]);
postordine[++nr]=x;
}
void dfst(int x){
viz[x]=0;
int i;
componenta[nrc][0]++;
componenta[nrc]=(int*)realloc(componenta[nrc],sizeof(int)*(componenta[nrc][0]+1));
componenta[nrc][componenta[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(g,"%d\n",nrc);
for(i=1;i<=nrc;i++){
for(j=1;j<=componenta[i][0];j++)
fprintf(g,"%d ",componenta[i][j]);
fprintf(g,"\n");
}
}