Цел: Да се намери гора с възможно най-много ребра, принадлежащи на неориентиран граф G с N върха и M ребра.

Идея на алгоритъма:

1. Започваме от гора, състояща се от всички върхове на G и без нито едно ребро в нея.

2. Четем ребрата едно по едно, правейки следното:

• Ако краищата на прочетеното ребро са от едно дърво в гората, игнорираме реброто.
• Ако краищата на прочетеното ребро са от различни дървета в гората, включваме реброто в гората и обединяваме дърветата, които реброто свързва.

Забележки:

1. Не се проверява коректност на данните.

Бързодействие:

Приведеният алгоритъм има сложност O(N^2).

Сходни задачи и допълнителни свойства:

• алгоритъмът изчислява свързаността на G:
  променливата cnt брои дървета в гората, т.е. тя е равна на броят на свързаните парчета в G.
  Едномерният масив C съдържа номера на дървета в гората, към които са закачени върховете на G.
  Проверката дали между два върха i и j има път в G е еквивалентна на условието C[i]=C[j].
• идеята на алгоритъма се използва при намиране на оптимално покриващо дърво, включително в жадният алгоритъм.

ИМЕ НА ЗАДАЧАТА: forest

ВХОДЕН ФОРМАТ:

* Ред 1: Цели числа N и M
  N е броят на върховете в графа (N<=1000), 
  M е броят на ребрата (неограничено), 

* Редове от 2 до M: 
  Всеки ред съдържа 2 параметъра: I и J, които описват ребро. 
  I и J са върховете, които реброто свързва.

ПРИМЕРЕН ВХОД (файл forest.in):

6 10
2 5
4 6
1 6
4 5
6 3
1 2
1 3
2 4
3 2
6 2


ИЗХОДЕН ФОРМАТ:

* редове 1..K: Съдържат ребрата от покриващата гора.
* ред K+1: Брой на дърветата в гората 

ПРИМЕРЕН ИЗХОД:

2 5
4 6
1 6
4 5
6 3
Брой на дърветата в гората: 1

• програма на Pascal
• примерни входни данни