Максимальное множество друзей Опции

[Jekaterina]

Доброй ночи! Не справляюсь с задачей: "В стране Н. пользуются порталом "Друзья". Во входном файле в первой строке дается номер максимально возмоной персоны, ниже приведены пары друзей, например:
15
2 4
6 11
2 13
13 2
4 14
Запись 2 4 означает, что персона 2 является другом персоны 4, и т. д. Друзья объединяются в множество друзей: например, из пар 2 4 и 2 13 образуется множество друзей {2, 4, 13}. Цель-отыскать наибольшее множество друзей и вывести его в выходной файл. Я думаю, здесь нужно использовать массив множеств, но не знаю, как правильно описать переменные (такая структура мне раньше не попадалась). Сам алгоритм мне тоже не ясен - может быть, кто-то из вас поймет, как использовать этот максимальный номер в первой строке? (надеюсь, динамические переменные здесь можно не использовать-я с ними пока крайне слабо знакома, а разобраться в решении хочется )Заранее благодарю за помощь!

[Bokul]

Вот, то как я понял алгоритм Michael_Rybak-а, только множества у меня не вышло присобачить.

const MaxN=128;
Var colors:array[1..MaxN] of integer;
    n:integer;

procedure WriteFile(s:string);//создаем файл
var f:file of integer;
begin
  assign(f,s);
  rewrite(f);
  write(f,44);
  write(f,5,6);
  write(f,4,44);
  write(f,1,3);
  write(f,4,2);
  close(f);
end;

function CountColor(color:integer):integer;//считаем сколько элементов в массиве colors имеют цвет color
var i,res:integer;
begin
  res:=0;
  for i:=1 to n do
      if colors[i]=color then
         inc(res);
  CountColor:=res;
end;

procedure Color(WhatColor,InColor:Integer);//закрашиваем все элементы массива colors цвета WhatColor в цвет InColor
var i:integer;
begin
  for i:=1 to n do
      if colors[i]=WhatColor then
         colors[i]:=InColor;
end;

function MaxColor:integer;//находим какого цвета большинство элементов
var i,j,res_color,buf_num,res_num:integer;
begin
  res_num:=0;
  res_color:=0;
  for i:=1 to n do
      begin
           buf_num:=0;
           for j:=i to n do
               if colors[i]=colors[j] then
                  inc(buf_num);
           if buf_num>res_num then
              begin
                   res_color:=colors[i];
                   res_num:=buf_num;
              end;
      end;
  MaxColor:=res_color;
end;

var   i,a,b,t:integer;
      f:file of integer;
begin
  WriteFile('friends.dat');
  assign(f,'friends.dat');
  reset(f);
  read(f,n);
  for i:=1 to n do
      colors[i]:=i;
  while not eof(f) do
        begin
             read(f,a,b);
             if colors[a]<>colors[b] then
                if CountColor(colors[a]) > CountColor(colors[b]) then
                   Color(colors[b],colors[a])
                else
                   Color(colors[a],colors[b]);
        end;
  close(f);
  t:=MaxColor;
  for i:=1 to n do
      if colors[i]=t then
         write(i,' ');
  readln;
end.

Сообщение отредактировано: Bokul - 2.01.2007 22:25

[Michael_Rybak]

Вот, то как я понял алгоритм Michael_Rybak-а, только множества у меня не вышло присобачить.

Хочу уточнить, что для того, чтобы получилось O(n log n), нужно хранить связный список для каждого цвета, а также количество элементов каждого цвета; тогда перекрашивание будет занимать O(min(N_A, N_B)), а проверка, какая группа меньше - O(1).

Могу привести код, у меня на С++ в заготовках это есть.

Это называется Система Непересекающихся Множеств.