并查集运算

今天看了下并查集运算。

并查集运算是用来操作集合的。它包含以下几个操作：

初始化：用于初始化并查集。

并运算：将2个集合合并

查运算：查找一个元素的父节点。

 

/*
 *    并查集
 */

/*
 * 将节点的父节点设置成自己
 */
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>

#define MAX 100
int    father[MAX];

#define ILLEGAL( x, n ) ( x<0 || x > n )

void set_init( int n )
{
    int i = 0;

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

/*
 * 查找x的父节点
 */

int set_find( int x )
{
    return father[x];
}

/*
 * 将x所在集合与y所在集合合并
 */

int set_union( int x, int y, int n )
{
    if( ILLEGAL(x,n) )
    {
        return 1;
    }
    if( ILLEGAL(y,n) )
    {
        return 1;
    }

    int father_x = 0;
    int father_y = 0;
    int father_i = 0;

    father_x = set_find( x );
    father_y = set_find( y );

    for( int i=0; i<n; i++ )
    {
        father_i = father[i];
        if( father_i == father_x )
        {
            father[i] = father_y;
        }
    }
}

void set_print( int n )
{
    for( int i=0; i<n; i++ )
    {
        printf( "%d ", father[i] );
    }
    printf( "\n" );
}

int    main()
{
    int n = 0;
    int x = 0;
    int y = 0;

    scanf( "%d", &n );

    set_init( n );
    set_print( n );

    for( int i=0; i<5; i++ )
    {
        printf( "input x, y\n" );
        scanf( "%d", &x );
        scanf( "%d", &y );

        set_union( x, y, n );
        set_print( n );
        printf( "end\n\n" );
    }

}