|
Темы:
Компоненты сильной связности
Применение обхода в глубину
Алгоритмы на графах
Поиск компонент связности
В далёком заснеженном города Снежнокрибирске очень мало пеших тропинок, так как город просто не успевает их чистить, потому люди передвигаются в основном только на внедорожниках: ездят в магазин, отвозят детей в школу, ездят на работу и так далее.
В один из последних дней перед зимними каникулами ребятам в школе задали проект на каникулы, который можно делать как самому, так и в группе, но не более 3 человек. Но так как проект связан с совместной работой, а в городе нет никакой связи: ни телефонной, ни интернета, то ребята решили собираться у кого-нибудь дома, чтобы делать проект вместе. Так как проект может делать до трёх человек, то ученики составили карту своих домов в городе, а также отметили на них тропинки. У них встал вопрос о том, как делать большинство проектов максимальным возможным количеством человек, но так, чтобы как можно меньше учеников делали проект одни. Помогите ребятам по описанию карты их города и тропинкам составить возможный план, как им лучше распределить проекты между собой.
Формат входных данных
На первой строке подаются два числа N, M (1 <= N,M <= 100) – количество домов и тропинок между ними соответственно.
Далее на M строках подаются дорожки в виде номеров домов (если существует дорога 1-2, то значит существует дорожка и 2-1).
Формат выходных данных
Выведите на первой строке количество учеников, которые делают проект в одиночку.
На второй – количество групп учеников, делающих проект в паре.
На третьей – количество групп учеников, делающих проект втроём.
Примечание: ребята стараются разбиться на группы по максимуму человек (по 3), если остался кто-то один, но он мог делать проект не один, то стараемся минимизировать одиночек.
|