接続性の問題--《Cアルゴリズム》学習ノート

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

typedef struct{
    int p;
    int q;
}pair;

/***************************************************************
                :
            ：      p   q       ,p q  。
      :   i       i，  0<=i<N。   p q      ,
        ，     p               q     .
      :     N   ，      M           ，
           O(M*N)
      : m:       , n: n   
***************************************************************/
void connectivity_quickfind(pair pairs[], int m, int id[], int n)
{
    int p, q, i, j, t;

    for (i = 0; i < n; ++i)
    {
        id[i] = i;
    }

    for (i = 0; i < m; ++i)
    {
        p = pairs[i].p;
        q = pairs[i].q;

        if (id[p] == id[q])   continue;

        for (t = id[p], j = 0; j < n; ++j)
        {
            if (id[j] == t) id[j] = id[q];
        }

        printf("%d, %d
", p, q);
    }
}

/***************************************************************
                :
                      。            
         ，          ，           。    
                ，             。
          M  ，              ，      ：
                     ，         。     ，
              (root)，          。
            ，    ,      N   、M       
        O(M*N/2)
***************************************************************/
void connectivity_quickunion(pair pairs[], int m, int id[], int n)
{
    int p, q, i, j, k;

    for (i = 0; i < n; ++i)
    {
        id[i] = i;
    }

    for (k = 0; k < m; ++k)
    {
        p = pairs[k].p;
        q = pairs[k].q;

        for (i = p; i != id[i]; i = id[i]);

        for (j = q; j != id[j]; j = id[j]);

        if (i == j) continue;

        id[i] = j;

        printf("%d, %d
", p, q);
    }
}

/***************************************************************
            ：
                ：               ，    
                    ，           。
      N            ，     2*lgN   。
***************************************************************/
void connectivity_weighted_quickunion(pair pairs[], int m, int id[], int n)
{
    int i, j, k, p, q;

    int *sz = (int *)malloc(n*sizeof(int));
    if (NULL == sz)
    {
        printf("
 No enough memory!!! 
");
        return;
    }

    for (i = 0; i < n; i++)
    {
        id[i] = i;
        sz[i] = 1;
    }

    for (k = 0; k < m; ++k)
    {
        p = pairs[k].p;
        q = pairs[k].q;

        for (i = p; i != id[i]; i = id[i]);

        for (j = q; j != id[j]; j = id[j]);

        if (i == j) continue;

        if (sz[i] < sz[j])
        {
            id[i] = j;
            sz[j] += sz[i];
        }
        else
        {
            id[j] = i;
            sz[i] += sz[i];
        }

        printf("%d, %d
", p, q);
    }

    free(sz);
}

/***************************************************************
                ：
***************************************************************/
void connectivity_pathcompression_weighted_quickunion(pair pairs[], int m, int id[], int n)
{
    int i, j, k, p, q;
    int *sz = (int *)malloc(n*sizeof(int));
    if (NULL == sz)
    {
        printf("
 No enough memory!!! 
");
        return;
    }

    for (i = 0; i < n; i++)
    {
        id[i] = i;
        sz[i] = 1;
    }

    for (k = 0; k < m; ++k)
    {
        p = pairs[k].p;
        q = pairs[k].q;

        //       
        for (i = p; i != id[i]; i = id[i])
        {
            id[i] = id[id[i]];
        }

        for (j = q; j != id[j]; j = id[j])
        {
            id[i] = id[id[i]];
        }

        if (i == j) continue;

        //   
        if (sz[i] < sz[j])
        {
            id[i] = j;
            sz[j] += sz[i];
        }
        else
        {
            id[j] = i;
            sz[i] += sz[i];
        }

        printf("%d, %d
", p, q);
    }
}
int main()
{
#if 1
    pair pairs[] = {
        { 3, 4 }, { 4, 9 }, { 8, 0 }, { 2, 3 },
        { 5, 6 }, { 2, 9 }, { 5, 9 }, { 7, 3 },
        { 4, 8 }, { 5, 6 }, { 0, 2 }, { 6, 1 },
        { 5, 8 },
    };
#else
    pair pairs[] = {
        { 0, 1 }, { 1, 2 }, { 2, 3 }, { 3, 4 },
        { 4, 5 }, { 5, 6 }, { 6, 7 }, { 7, 8 },
        { 8, 9 }, { 9, 0 }, 
    };
#endif

    int m = sizeof(pairs) / sizeof(pairs[0]);
    int n = 10;
    int id[10];

    printf("
connectivity_quickfind:
");
    connectivity_quickfind(pairs, m, id, n);
    printf("
connectivity_quickunion:
");
    connectivity_quickunion(pairs, m, id, n);
    printf("
connectivity_weighted_quickunion:
");
    connectivity_weighted_quickunion(pairs, m, id, n);
    printf("
connectivity_pathcompression_weighted_quickunion:
");
    connectivity_pathcompression_weighted_quickunion(pairs, m, id, n);

    return 0;
}