«Реализация жадного алгоритма на c++»

Формулировка задачи: В некоторой Галактике силы правопорядка выявили разветвленную шпионскую сеть. Сеть сильно законспирирована и состоит из рядовых членов и руководителей различных уровней. Во главе стоит один главный руководитель — лидер. До начала арестов приказ лидера может быть доведен до любого члена сети. Все члены сети пронумерованы от 1 до N. Каждый член сети знает только своего вышестоящего руководителя (ровно одного) и своих непосредственных подчиненных (руководитель не знает подчиненных своего подчиненного и наоборот). Естественно, что с началом арестов членов сети она распадется на мелкие, не связанные друг с другом группы. Например, с арестом члена сети № 2 (рисунок) сеть разваливается на 4 группы. Полицмейстер уверяет, что группа, состоящая из менее чем К членов сети, вырождается и не представляет угрозы. Стремясь не уронить престиж Галактики, полицмейстер поставил задачу произвести минимальное количество арестов членов сети так, чтобы от нее остались только вырождающиеся маленькие группы.

Требуется: Написать программу, которая бы по входным данным, описывающим структуру подпольной партии, выводила количество арестов и номера членов партии, которых нужно арестовать.

Входные данные: файл ORG.IN Входной файл содержит три строки. В первой записано число K (1 ≤ K ≤ 10 000), во второй строке — число N (1 ≤ N ≤ 10 000), определяющее количество членов партии. Третья строка содержит набор из N—1 числа. В этой строке для каждого члена партии, кроме лидера, задается номер его непосредственного руководителя. Номер руководителя всегда меньше, чем номер подчиненного. При этом первое число задает номер руководителя второго члена партии, второе — третьего и так далее. Числа в строке разделяются одним пробелом.

Выходные данные: файл ORG.OUT Выходной файл состоит из двух строк. В первую строку необходимо поместить количество арестов, а во вторую — номера членов партии, подлежащих аресту. Эти номера разделяются одним пробелом. При наличии нескольких решений выведите одно из них.

Пример входного файла для структуры партии, представленной на рисунке:

• 3
• 14
• 1 1 2 2 3 2 3 6 6 6 7 4 7

Пример выходного файла для приведенного входного файла:

• 4
• 6 2 7 8