#include #include #include #define PROBABILITY0 0.64 #define PROBABILITY1 0.32 typedef struct _node { int size; struct _node *P; } node; typedef node **MFT; char **genmesh ( int n ) { char **A; int i, j; double x, probability; srand((unsigned int)time(NULL)); probability = (rand() % 2) ? PROBABILITY1 : PROBABILITY0; printf("*** Blocking probability = %4.2lf\n", probability); A = (char **)malloc((n+1) * sizeof(char *)); for (i=0; i<=n; ++i) A[i] = (char *)malloc(n * sizeof(char)); for (j=0; j P) p = p -> P; return p; } void mergesets ( node *p, node *q ) { if (p -> size <= q -> size) { p -> P = q; q -> size += p -> size; } else { q -> P = p; p -> size += q -> size; } } void mergeregions ( char **A, int n, MFT T ) { int i, j; node *p, *q; for (i=0; i<=n; ++i) for (j=0; j 0) && (A[i-1][j] == '1')) { p = findset(T,i-1,j); q = findset(T,i,j); if (p != q) mergesets(p,q); } if ((j > 0) && (A[i][j-1] == '1')) { p = findset(T,i,j-1); q = findset(T,i,j); if (p != q) mergesets(p,q); } } } void findreach ( char **A, int n, MFT T ) { node *p; int i, j; p = findset(T,0,0); for (i=0; i<=n; ++i) for (j=0; j 1) n = atoi(argv[1]); else scanf("%d", &n); printf("n = %d\n", n); A = genmesh(n); printf("\n+++ Input mesh\n"); printmesh(A,n); T = initsets(n); mergeregions(A,n,T); for (j=0; j