да, точно.
могут же быть циклы в компонентах связности.
А так хотелось проверять "жлобским методом" 
26 2011-04-03 20:13:55
Re: Определить или граф есть деревом (3 ответов, оставленных в Algo)
27 2011-04-03 00:14:36
Тема: Определить или граф есть деревом (3 ответов, оставленных в Algo)
Задача:
Определить или неориентированнй взвешенный граф является деревом.
Решить просто: количество ребер должно быть N-1 (где N - количество вершин) и запустить поиск в глубину - проверить связность.
Но посетила мысль! А нельзя ли проще:
проверить количество ребер, что б было N-1 и проверить что б не было вершин со степенью 0. (иключение вариант с одной вершиной).
Верен ли этот метод?
28 2011-03-26 02:04:03
Re: ЛКШ 2010 (9 ответов, оставленных в OlympNews)
качнул эту ссылку. круто
Держи smile http://depositfiles.com/files/yloggr0ol
а есть ещ наборы с других месяцев или годов?
29 2011-03-26 01:02:53
Re: Количество разложений числа на множители N<=2*10^9 (5 ответов, оставленных в Problems)
ну собственно в первом посте я писал "рекурентную формулу с запоминанием результатов" что и подразумевало динамику.
Но меня интересует нет ли других путей.
Можетесть комбинаторная формула от набора простых делителей?
Т.е. формула зависимости ответа от степеней вхождения простых множителей в число
30 2011-03-25 16:25:51
Re: Количество разложений числа на множители N<=2*10^9 (5 ответов, оставленных в Problems)
aza_inf пишет:
И получится что-то вот такое:
p1^a1 * p2^a2 * ... pk^ak, где pi - это i-тое простое число
Ответом будет (a1+1)*(a2+1)*...(ak+1)Например, если N=100, то 100 = 2^2 * 5^2, и ответ = (2+1)*(2+1) = 3*3 = 9.
нет. эта формула дает КОЛИЧЕСТВО ДЕЛИТЕЛЕЙ ЧИСЛА.
А оно не совпадает с количеством разбиений.
у числа 30 разбиений 4 (если включать еще вариант 1*30 то 5 разбиений) а делителей 8 (включая 1 и 30)
31 2011-03-25 00:04:03
Тема: Количество разложений числа на множители N<=2*10^9 (5 ответов, оставленных в Problems)
Дано число N в пределах до двух миллиардов.
Определить сколько есть разложений числа на множители.
6 = 2 * 3
6 = 3 * 2
являются одинаковыми разложениями.
так для числа 12 все разбиения будут
2*6
2*2*3
3*4
для числа 30 разбиения будут
2*3*5
2*15
3*10
5*6
По заданному N определить количество разбиений.
Какие идеи к решению задачи?
Первое что приходит на ум - разложить на простые множители, а далее писать рекурентную формулу с запоминанием результатов.
Но все как то муторно.
Есть проще и изящнее решения?