Felix021

#include <stdio.h>
#include <stdlib.h>

/*
* Kruskal贪心算法求最小生成树(heap+并查集)
* 测试输入数据：

6 10 //6个顶点10条边
1 5 2  //从顶点1到顶点5的边权重为2
2 4 3
4 5 1
0 3 6
2 3 7
5 2 6
4 0 7
1 3 5
1 2 4
3 5 9

*/

struct edge {
    int start, end, weight;
};

void siftdown (struct edge *a, int n, int i) {
    struct edge t;
    if (i < 1 || i > n) return;
    while (i * 2 <= n) {
        i *= 2;
        if (i + 1 <= n && a[i].weight > a[i + 1].weight) i++;
        if (a[i].weight < a[i/2].weight ) {
            t = a[i];
            a[i] = a[i/2];
            a[i/2] = t;
        }
        else {
            break;
        }
    }
}

void siftup (struct edge *a, int n, int i) {
    struct edge t;
    if (i < 1 || i > n) return;
    while (i > 1) {
        if (a[i].weight < a[i/2].weight) {
            t = a[i];
            a[i] = a[i/2];
            a[i/2] = t;
        }
        else {
            break;
        }
        i /= 2;
    }
}

void makeheap(struct edge *a, int n) {
    int i;
    for (i = n / 2; i >= 1; --i) {
        siftdown(a, n, i);
    }
}

struct edge pop(struct edge *a, int *n) {
    struct edge t;
    t = a[1];
    a[1] = a[*n];
    (*n)--; //第二次挂在这里，不能写*n--(*n; n-=1;), 要写(*n)--
    siftdown(a, *n, 1);
    return t;
}

void dump(struct edge *a, int n) {
    int i;
    for (i = 0; i < n; ++i) {
        printf("edge (%d, %d), %d\n", a[i].start, a[i].end, a[i].weight);
    }
}

void initUnionSet(int a[], int n) {
    int i;
    for (i = 0; i < n; ++i) {
        a[i] = i;
    }
}

int getFather(int a[], int x) {
    return a[x] == x ? x : (a[x] = getFather(a, a[x]));
}

void merge(int a[], int x, int y) {
    x = getFather(a, x);
    y = getFather(a, y);
    a[x] = y;
}

int haveCommonAncestor(int a[], int x, int y) {
    return (getFather(a, x) == getFather(a, y) ? 1 : 0);
}


int main () {
    int m, n, i, k, *father;
    struct edge *input, *output, t;

    scanf("%d%d", &m, &n);
    input = (struct edge *)malloc(sizeof(struct edge) * (n + 1));
    for (i = 1; i <= n; ++i) {
        scanf("%d%d%d", &input[i].start, &input[i].end, &input[i].weight);
    }
    makeheap(input, n);
    dump(input+1, n);
    printf("end input\n");
    
    int n1 = n;
    output = (struct edge *)malloc(sizeof(struct edge) * (m - 1));
    father = (int *)malloc(sizeof(int) * n);
    initUnionSet(father, m);
    k = 0;
    printf("\nStart:\n");
    while (n1 > 0) {
        t = pop(input, &n1);
        printf("edge (%d,%d), %d ", t.start, t.end, t.weight);
        if (0 == haveCommonAncestor(father, t.start, t.end)) {
            printf("added in\n");
            output[k] = t;
            k++;
            merge(father, t.start, t.end);
            if (k == m - 1) {
                printf("~~ok~~\n");
                break;
            }
        }
        else {
            printf("ignored\n");
        }
    }
    printf("\nresult:\n");
    dump(output, k);

    free(input);
    free(output);
    free(father);
    return 0;
}

#include <stdio.h>
#include <stdlib.h>
#ifdef __GNUC__
    #define WARN_IF_UNUSED __attribute__ ((warn_unused_result))
#else
    #define WARN_IF_UNUSED
#endif


struct node {
    int v;
    struct node *next;
};

struct linklist {
    struct node *head;
    struct node *tail;
};

WARN_IF_UNUSED int init(struct linklist ll[], int n) {
    int i;
    for (i = 0; i < n; ++i) {
        ll[i].head = (struct node *)malloc(sizeof(struct node));
        if (ll[i].head == NULL) {
            return 0;
        }
        ll[i].head->next = NULL;
        ll[i].tail = ll[i].head;
    }
    return 1;
}

void dump(struct linklist *ll) {
    struct node *p = ll->head->next;
    while (p != NULL) {
        printf("%d ", p->v);
        p = p->next;
    }
    printf("\n");
}

WARN_IF_UNUSED int push(struct linklist *ll, int v) {
    struct node *p = (struct node *)malloc(sizeof(struct node));
    if (p == NULL) {
        return 0;
    }
    p->v = v;
    p->next = NULL;
    ll->tail->next = p;
    ll->tail = p;
    return 1;
}

int isEmpty(struct linklist *ll) {
    return (ll->head->next == NULL) ? 1 : 0;
}


int pop(struct linklist *ll) {
    if (isEmpty(ll)) {
        exit(1);
    }
    struct node *p = ll->head;
    ll->head = p->next;
    free(p);
    return ll->head->v;
}

void radixSort(int a[], int n) {
    struct linklist ll[10];
    int flag, i, j, t, fact = 1;
    if (init(ll, 10) == 0) {
        exit(2);
    }
    do {
        printf("---------------\n");
        flag = 0;
        for (i = 0; i < n; ++i) {
            t = a[i] / fact % 10;
            flag += !!t;
            //printf("%d: %d\n", a[i], t);
            if (push(&ll[t], a[i]) == 0) {
                exit(2);
            }
        }
        for (i = 0, j = 0; i < 10; ++i) {
            printf("%d: ", i);
            dump(&ll[i]);
        }
        for (i = 0, j = 0; i < 10; ++i) {
            while (isEmpty(&ll[i]) == 0) {
                a[j] = pop(&ll[i]);
                j++;
            }
        }
        fact *= 10;
    }while (flag != 0);
}

int main() {
    int a[] = {26,62,187,32,8754359,45324,54654,0,331,321312,12,4324,87,98};
#define N (sizeof(a) / sizeof(int))
    radixSort(a, N);
    int i;
    for (i = 0; i < N; ++i) {
        printf("%d ", a[i]);
    }
    printf("\n");
    return 0;
}