disjoint의 성질을 이용해서 UNION을 사용한 미로 만들기

Study

disjoint의 성질을 이용해서 UNION을 사용한 미로 만들기

bslime 2009. 5. 9. 19:57

#include <stdio.h>
#include <stdlib.h>
int * parent;
int * rank;
void MAKE_SET(int p);
int FIND(int find);
void UNION(int x, int y);
int main(void) {
    int p, q, count = 0;
    int i, j, qsetname, psetname;
    int gaid = 1, seid = 1;
    int t = 20, t2 = 10;
    int ground, n;
    printf("input number n <= 50");
    printf("\n");
    scanf("%d", & amp; n);
    ground = n * n;
    /** lg1 = new Line(10, 10, $n*10+10, 10); **/
    /** lg2 = new Line(10, $n*10+10, $n*10+10, $n*10+10); **/
    /** ls2 = new Line($n*10+10, 10, $n*10+10, $n*10+10); **/
    while (gaid & lt; ground) {
        for (i = 1; i & lt; = n; i++) {
            /** ga$gaid = new Line($i*10, $t,($i+1)*10, $t); **/
            gaid++;
        }
        t += 10;
    }
    while (seid & lt; ground) {
        for (i = 1; i & lt; = n; i++) {
            /** se$seid = new Line($i*10,$t2, $i*10, $t2+10); **/
            seid++;
        }
        t2 += 10;
    }
    parent = (int * ) malloc(sizeof(int) * (ground + 1));
    rank = (int * ) malloc(sizeof(int) * (ground + 1));
    if (parent && rank == NULL) exit(1);
    MAKE_SET(ground);
    while (count & lt; ground - 1) {
        p = (rand() % ground) + 1;
        q = (rand() % 4);
        if (q == 0) q = p - 1;
        else if (q == 1) q = p + 1;
        else if (q == 2) q = p - n;
        else q = p + n;
        if (q % n == 0 && p % n == 1) continue;
        if (p % n == 0 && q % n == 1) continue;
        if (q & gt; 0 && q & lt; ground) {
            if ((psetname = FIND(p)) != (qsetname = FIND(q))) {
                if (q == p - n || q == p + n) {
                    if (p & lt; q) {
                        /**remove(ga$p); **/
                    } else { /**remove(ga$q); **/
                    }
                } else if (q == p + 1 || q == p - 1) {
                    if (p & lt; q) { /**remove(se$q); **/
                    } else { /**remove(se$p); **/
                    }
                }
                count++;
                UNION(psetname, qsetname);
            }
        }
    }
    free(parent);
    free(rank);
}
void MAKE_SET(int p) {
    int make;
    for (make = 1; make & lt; = p; make++) {
        parent[make] = make;
        rank[make] = 0;
    }
    printf("\n");
}
int FIND(int find) {
    if (find != parent[find]) parent[find] = FIND(parent[find]);
    return parent[find];
}
void
UNION(int x, int y) {
    int u, v;
    u = FIND(x);
    v = FIND(y);
    if (rank[u] & gt;
    rank[v]) parent[v] = u;
    else {
        parent[u] = v;
        if (rank[u] == rank[v]) rank[v]++;
    }
}

중간중간주석으로표기되어있는부분은CAS와연동되는부분,
주석의자비란없습니다, -_ - ;