Группы кабинетов по коридорам

В школе есть n кабинетов, пронумерованных от 1 до n. Между некоторыми парами кабинетов проложены коридоры. По коридору можно пройти в обе стороны.

Директор хочет понять, на сколько «изолированных крыльев» разбивается школа: кабинеты считаются в одном крыле, если из одного можно добраться до другого, проходя по коридорам.

Найдите количество таких крыльев (компонент связности) и размеры всех крыльев.

Коридоры могут повторяться, а также может встретиться коридор из кабинета в этот же кабинет — на ответ это не влияет.

Формат ввода

Первая строка: два целых числа n и m — число кабинетов и число коридоров. Далее идут m строк: по два целых числа u и v (1 ≤ u, v ≤ n) — коридор между кабинетами u и v.

Формат вывода

В первой строке выведите число k — количество компонент связности. Во второй строке выведите k чисел — размеры компонент, отсортированные по неубыванию.

Ограничения

1 ≤ n ≤ 8000 0 ≤ m ≤ 8000 Время: 2 секунды. Память: 256 МБ.

Пример

Ввод:

6 3
1 2
2 3
5 6

Вывод:

3
1 2 3

Ключевое наблюдение: «крыло» — это просто компонентa связности в неориентированном графе. Если из кабинета можно дойти до других по коридорам, то все они окажутся в одной компоненте. Поэтому достаточно много раз запускать обход (DFS или BFS), каждый раз собирая все вершины, достижимые из стартовой.

Почему работает: DFS/BFS гарантирует, что мы посетим ровно те кабинеты, до которых есть путь. Повторяющиеся коридоры и петли (u = v) не мешают: они либо ведут в уже посещённую вершину, либо в ту же самую.

План:

• Считать n, m и построить список смежности: для каждого коридора добавить v в g[u] и u в g[v].
• Завести массив used[1..n] = False.
• Для каждого кабинета s от 1 до n:
• если used[s] уже True, пропустить;
• иначе запустить обход из s (лучше итеративный стек/очередь), помечая used и считая, сколько вершин посетили — это размер текущего крыла.
• Сложить все размеры в список, отсортировать по неубыванию.
• Вывести количество компонент и отсортированные размеры.

Мини-сниппет идеи подсчёта: cnt = 0; while stack: v = stack.pop(); cnt += 1

Сложность: O(n + m) на все обходы + O(k log k) на сортировку размеров (k — число компонент).

Частая ошибка: рекурсивный DFS в Python может упереться в лимит рекурсии; безопаснее использовать собственный стек (итеративный DFS) или BFS с очередью.