Задача с олимпиады
районов области. Известно, что:
- Количество человек в каждой команде может быть любое — от I до N;
- Каждый участник соревнований получил индивидуальный порядковый номе^ от I до N, никак не связанный с номером команды;
- В каждой команде оказались только знакомые люди (либо непосредственно, либо через другого/других членов этой же команды);
- Известны все пары участников соревнований, непосредственно знакомых друг с другом (также считается, что каждый человек знаком сам с собой).
- Участники различных команд не знакомы ни лично, ни опосредовано через других людей.
Ограничения 1 <= n <=200, время 1 с.
Технические требования:
Входной файл COMP.1N.
Выходной файл COMP.OUT.
Внимание! На тестирование принимается исполнимый файл, который дол¬жен иметь имя, соответствующих именам входного и выходного файлов задачи (т.e.COMР.ЕХЕ).
Формат входных данных:
В первой строке входного файла содержится одно натуральное число п (1<п<200).
Во всех остальных строках содержатся разделенные пробелом пары натуральных чисел х (1 < х < п) и у (I < у < п), причем пары могут повторяться произвольное количест¬во раз. Если ни один человек не знаком ни с одним другим, то во входном файле содер¬жится только одна строка с одним натуральное число n (1 < п < 200)
Формат выходных данных:
Выходной файл содержит единственное натуральное число - количество команд
Примеры файлов входных и выходных данных:
З.Ы. Если кому интересно, могу другие выложить, некоторые с решением.
А по подробней, граф т.е. используя графику?
То есть для формирования очередной группы нужно выделить ее подграф путем обхода его ребер, связывающих вершины - индивидуальные порядковые номера знакомых участников. Хотя бы можно так:
1. Ищем очередную не отмеченную вершину.
2. Отмечаем ее как пройденную.
3. Определяем список связанных с ней вершин.
4. Для каждой такой вершины из списка, если вершина еще не пройдена, возвращаемся к шагу 2 рекурсивно.
5. Очередная группа определена. Возвращаемся к шагу 1 для определения следующей.
6-е место у меня, а 5-е уже считается призовым.
А за ссылку спасибо :)
...
То есть для формирования очередной группы нужно выделить ее подграф путем обхода его ребер, связывающих вершины - индивидуальные порядковые номера знакомых участников. Хотя бы можно так:
1. Ищем очередную не отмеченную вершину.
2. Отмечаем ее как пройденную.
3. Определяем список связанных с ней вершин.
4. Для каждой такой вершины из списка, если вершина еще не пройдена, возвращаемся к шагу 2 рекурсивно.
5. Очередная группа определена. Возвращаемся к шагу 1 для определения следующей.
Я так прикинул, суть и без графов понятна. Если бы они помогли помочь в реализации программы на стадии кодирования – другое дело. Все упирается в код.
Была бы ясна суть алгоритма, а код, как говорится, не проблема. В чем конкретно загвоздка в коде тогда?
Я представляю себе решение в виде цикла где за одну итерацию от массива(с номерами команд) отсекается ровно одна команда, так вот как отсечь от массива все связанные номера??
Ну хотя бы в самом простом случае их (найденные связанные номера) отмечать как-нибудь и в следующей итерации не просматривать. Pascal под рукой нет, но в общем виде код будет содержать нечто следующее:
{ массив пар }
M = array[1..200, 1..2] of integer;
{ вспомогательный массив для отметки идентификаторов проверенных участников }
T = array[1..200] of integer;
var
C, groups_total, i: integer;
procedure familiarity(id: integer);
var
j: integer;
begin
T[id] := 1;
for j := 1 to C do
begin
if M[j][1] = id and T[M[j][2]] = 0 then familiarity(M[j][2]);
if M[j][2] = id and T[M[j][1]] = 0 then familiarity(M[j][1]);
end;
end;
begin
{ ...читаем количество пар в переменную C... }
{ ...читаем пары в массив M... }
for i := 1 to 200 do T := 0;
groups_total := 0;
for i := 1 to C do
begin
if T[M[1]] = 0 then
begin
groups_total := groups_total + 1;
familiarity(M[1]);
end;
end;
{ groups_total содержит количество выделенных групп со знакомыми участниками }
end.
Если участник n ни с кем не знаком, то пара должна содержать значение [n, n]. Вариант далеко не оптимален, да и я не особый специалист по этому.