Решил задачу на codingame.com под название "Teads Sponsored Challenge", проходят все тесты, кроме четырех.
В этих четырех тестах по сравнению с остальными существенно увеличивается количество входных данных, а дают на входе количество ребер одним числом и в цикле - ребра (Вот так - "371 290", тип строковый). К слову, ребра перечисляются вразброс, то есть не отсортировано, 95 462, 461 364, 322 54, 300 359, 256 333, 64 157.
Я использовал двумерный массив, чтобы хранить ребра и написал рекурсивную функцию, чтобы проверять наличие соседей у вершин. Принцип работы программы следующий: собрал всю входную информацию, создал массив для хранения результата работы рекурсивной функции для каждой из вершин.
Но по таймауту не проходят остальные тесты, успевает обработать всего около 120 вершин, например из 546. Подозреваю, что проблема заключается в том, что я использую двумерный массив, как следствие при поиске соседей у вершины приходится обходить оба измерения массива.
Как можно сделать правильнее, лучше, быстрее?
К слову, код пишу в VS, а проверить выполнение тестов могу только на сайте, то есть написал код, скопировал и вставил в редактор кода на самом сайте, запустил тесты, получил результат. Отлаживать там можно только через Console.Error.WriteLine().
O(N^2)
вместоO(log N)
. (Конкретнее сказать не могу, задание не видел.)