weiss_f_08_06.cpp

Tianjin University Online Judge 的80多道题目 .

#include<cstdio>
#define NumSets 100

typedef int DisjSet[ NumSets + 1 ];
typedef int SetType;
typedef int ElementType;

void initialize( DisjSet set );
void setUnion( DisjSet set , SetType Root1 , SetType Root2 );
SetType find( Element x , DisjSet set );

void initialize( DisjSet set )
{
  int i ;
  for ( i = NumSets; i > 0; i-- )
    set[ i ] = -1;
}

void setUnion1( DisjSet set , SetType Root1 , SetType Root2 )
{
  set[ Root2 ] = Root1;
}

void setUnion2( DisjSet set , SetType Root1 , SetType Root2 )
{
  if ( set[ Root2 ] < set[Root1 ] )
    set[ Root1 ] = Root2;
  else if ( set[ Root1 ] < set[ Root2 ] )
    set[ Root2 ] = Root1;
  else
    {
      set[ Root1 ] --;
      set[ Root2 ] = Root1;
    }
}
    

SetType Find( ElementType key , DisjSet set )
{
  if ( set[ key ] <= 0 )
    return key;
  else
    return find( set[ key ] , set );
}

SetType find( Element key , DisjSet set )
{
  if ( set[ key ] <= 0 )
    return key;
  else
    return set[ x ] = find( set[ key ] , set );
}