#include #define GRAPHE "graphe" #define NMAX 32 typedef struct { int n; int mat[NMAX][NMAX]; } Graph; Graph read(char *name) { int i,j; Graph r; FILE *fp; fp = fopen(name,"r"); if (fp == NULL) { fprintf(stderr,"Je ne peux pas ouvrir %s\n",name); exit(-1); } fscanf(fp,"%d",&r.n); for (i = 0 ; i < r.n ; i++) for (j = 0 ; j < r.n ; j++) fscanf(fp,"%d",&r.mat[i][j]); fclose(fp); return r; } void trans(Graph *r,Graph g) { int i,j,k; int n = g.n; r->n = n; for (i = 0 ; i < n ; i++) for (j = 0 ; j < n ; j++) r->mat[i][j] = g.mat[i][j]; for (k = 0 ; k < n ; k++) for (i = 0 ; i < n ; i++) for (j = 0 ; j < n ; j++) if (!r->mat[i][j]) r->mat[i][j] = r->mat[i][k] && r->mat[k][j]; } void cfc(Graph g) { int n = g.n; int i,j; Graph g_star; /* fermeture transitive */ int r[NMAX]; /* r[i] est le plus petit sommet contenu dans le cfc du sommet i */ /* calcul de la fermeture transitive */ trans(&g_star,g); for (i = 0 ; i < n ; i++) r[i] = -1; for (i = 0 ; i < n ; i++) if (r[i] != -1) ; /* deja vu */ else { r[i] = i; printf("%d ",i+1); for (j = i+1 ; j < n ; j++) if (g_star.mat[i][j] && g_star.mat[j][i]) { r[j] = i; printf("%d ",j+1); } printf("\n"); } } void main(void) { Graph g; g = read(GRAPHE); cfc(g); }