Быстрый переход Новости Основы файлового ввода вывода Структуры данных Теория графов Геометрия - основы планиметрии Математические алгоритмы Геометрия - основы стереометрии

• Новости
• Алгоритмы
  • Структуры данных
  • Теория графов
  • Геометрия
  • Стереометрия
  • Математика

Непересекающиеся множества

Непересекающиеся множества предназначены для выполнения запросов:

1. Найти номер множества, в котором встречается данный элемент
2. Объединить два множества в одно

Каждый элемент должен встречаться только в одном множестве.

Листинг Delphi

const DisetLength = 10000;
type Diset = object
       public
         p, rank : array[1..DisetLength] of integer;
       public
         constructor Create; overload;
         constructor Create(N : integer); overload;
         procedure MakeSet(x : integer);
         procedure Union(x, y : integer);
         procedure Link(x, y : integer);
         function FindSet(x : integer) : integer;
     end;

implementation

constructor Diset.Create;   
  begin
    FillChar(rank, sizeof(rank), 0);
  end;

  constructor Diset.Create(N : integer); // Создание системы из n множеств
    var i : integer;
  begin
    for i := 1 to N do
      begin
        p[i] := i;
        rank[i] := 0;
      end;
  end;

  procedure Diset.MakeSet(x : integer);
  begin
    p[x] := x;
    rank[x] := 0;
  end;

  procedure Diset.Union(x, y : integer);   // Объединение множеств, содержащих элементы x и y
  begin
    Link(FindSet(x), FindSet(y));
  end;

  procedure Diset.Link(x, y : integer); 
  begin
    if rank[x] > rank[y]
      then p[y] := x
      else begin
             p[x] := y;
             if rank[x] = rank[y]
               then inc(rank[y]);
           end;
  end;

  function Diset.FindSet(x : integer) : integer; // Индекс множества, содержащего элемент
    var y : integer;
  begin
    y := x;
    while p[y] <> y
      do y := p[y];
    p[x] := y;
    Result := y;
  end;

Листинг C++

const int MaxN = 10000;
class diset
{
public:
    int n;
    int p[MaxN];
    int r[MaxN];
    int count;

    diset(int _n);
    int find(int i);
    void link(int i, int j);
    int size();
};
diset :: diset(int _n)   // Создание системы из n множеств
{
    n = _n;
    count = _n;
    for (int i = 0; i < n; ++ i)
    {
        p[i] = i;
        r[i] = 0;
    }
}
int diset :: find(int i)   // Поиск множества, содержащего элемент i
{
    if (i != p[i])
        p[i] = find(p[i]);
    return p[i];
}
void diset :: link(int i, int j) // Объединение двух множеств
{
    count -= (find(i) != find(j));

    if (r[find(i)] < r[find(j)])
        p[find(i)] = p[find(j)];
    else
    {
        p[find(j)] = p[find(i)];
        if (r[find(i)] == r[find(j)])
            ++ r[find(i)];
    }
}    

08.12.2007, 18:37