Question

21.1 不相交集合上的操作

21.1-1

Input:d i
Output:a b c e f g h i j k
Input:f k
Output:a b c e g h i j k
Input:g i
Output:a b c e h i j k
Input:b g
Output:a c e h i j k
Input:a h
Output:c e h i j k
Input:i j
Output:c e h i k
Input:d k
Output:c e h i
Input:b j
Output:c e h i
Input:d f
Output:c e h i
Input:g j
Output:c e h i
Input:a e
Output:c h i
Press any key to continue

21.1-3

FIND-SET 2|E|次

UNION |E|次

21.2 不相交集合的链表表示

21.2-1

void Make_Set(int x)
{
  S[x].head = x;
  S[x].tail = x;
  S[x].size = 1;
  n[x].rep = x;
  n[x].next = 0;
}
int Find_Set(int x)
{
  return n[x].rep;
}
void Union(int x, int y)
{
  x = n[x].rep;
  y = n[y].rep;
  if(S[x].size >S[y].size)
    swap(x, y);
  n[S[y].tail].next = S[x].head;
  S[y].size = S[y].size + S[x].size;
  int i;
  for(i = S[x].head; i != 0; i = n[i].next)
    n[i].rep = y;
  S[x].head = 0;
}

21.2-2

16

16

21.2-5

void Union2(int x, int y)
{
  x = n[x].rep;
  y = n[y].rep;
  if(x == y)
    return ;
  if(S[x].size >S[y].size)
    swap(x, y);
  S[y].size = S[y].size + S[x].size;
  int i;
  for(i = S[x].head;; i = n[i].next)
  {
    n[i].rep = y;
    if(n[i].next == 0)
    {
      n[i].next = n[S[y].head].next;
      break;
    }
  }
  n[S[y].head].next = S[x].head;
  S[x].head = 0;
}

 

21.3 不相交集合森林

21.3-2

void UFS::Find_Set2(int x)
{
  int ret = x, t;
  while(ret != p[ret])
    ret = p[ret];
  while(p[x] != ret)
  {
    t = p[x];
    p[x] = ret;
    x = p[x];
  }
}

21.3-3

题目的意思不懂