Путешествие по мирам

@Natasha2005 · Регистрация: 24.11.2021

Студворк — интернет-сервис помощи студентам

Путешественник Мориорти любит путешествовать между мирами. Он знает n миров. Массив a описывает n порталов, с помощью которых он может перемещаться между 2-мя мирами. i-ый портал означает следующее: из i-ого мира существует возможность переместиться в ai-ый мир. Портал перемещает только в одну сторону. Если портал ведет из i-го в j-ый мир, то из j-го в i-ый мир по этому порталу попасть нельзя.В массиве все числа различны. Формально говоря, изначально у Мориорти не существует мира, в который ведет более 1-го портала. У Мориорти могут существовать порталы, которые перемещают в тот же мир в котором они находятся.
В массиве все числа различны. Формально говоря, изначально у Мориорти не существует мира, в который ведет более 1-го портала. У Мориорти могут существовать порталы, которые перемещают в тот же мир в котором они находятся.
К сожалению, Мориорти из некоторых миров не может попасть в некоторые другие, даже если он будет перемещаться через несколько порталов. Мориорти может построить еще несколько порталов. Но количество порталов ограничено. Помогите Мориорти определить минимальное количество новых порталов, которые ему нужно построить, чтобы попасть из любого мира в любой другой.
Например, рассмотрим массив a=[1,4,2,3,5]. На рисунке 1 показаны связи с мирами. На втором рисунке показано возможное решение.

Формат ввода

В первой строке дано одно число n(1≤n≤105) — количество миров.
В следующей строке даны n чисел (1≤ai≤n) — информация об изначальных порталах.

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

Выведите одно число — ответ на задачу

Пример 1

Ввод

5
1 2 3 4 5

Вывод

5

Пример 2

Ввод

5
2 3 4 5 1

Вывод

0

@eaa · 24.11.2021, 14:59

Natasha2005, и что конкретно не получается?

@idealist · 25.11.2021, 00:24

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#===============================================================================
def get_cycles_counter(indexes, worlds, cycles_counter):
    i = indexes[0]
    cur_cycle = [i]
    
    while True:
        indexes.remove(i)
        i = worlds[i] - 1
        cur_cycle.append(i)
        if i == cur_cycle[0]:
            return cycles_counter + 1
#===============================================================================
def count_cycles(worlds):
    indexes = []
    for i in range(len(worlds)):
        indexes.append(i)
        
    cycles_counter = 0
    
    while len(indexes):
        cycles_counter = get_cycles_counter(indexes, worlds, cycles_counter)        
 
    return cycles_counter
#===============================================================================
def count_portals(worlds):
    res = count_cycles(worlds)
 
    if res == 1:
        res = 0;
    return res;
#===============================================================================
import random
n = 5
worlds = [1, 2, 3, 4, 5]
random.shuffle(worlds)
print('worlds = ', worlds)
 
print(count_portals(worlds))

@eaa · 25.11.2021, 05:28

idealist, O(n^2).
а тут решение O(n)

@idealist · 25.11.2021, 05:39

Еще вариант:

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#===============================================================================
def remove_cur_cycle_indexes(indexes, worlds):
    i = indexes[0]
 
    while True:
        indexes.remove(i)
        i = worlds[i] - 1
        if i not in indexes:
            break;
#===============================================================================
def count_cycles(worlds):
    indexes = list(range(len(worlds)))
    cycles_counter = 0
    
    while len(indexes):
        remove_cur_cycle_indexes(indexes, worlds)
        cycles_counter += 1
 
    return cycles_counter
#===============================================================================
def count_portals(worlds):
    res = count_cycles(worlds)
 
    if res == 1:
        res = 0
    return res
#===============================================================================
import random
n = 5
worlds = [1, 2, 3, 4, 5]
random.shuffle(worlds)
print('worlds = ', worlds)
 
print(count_portals(worlds))

@eaa · 25.11.2021, 05:42

idealist, по одной строке можно определить что это тот же O(n^2)

@idealist · 25.11.2021, 05:42

Сообщение от eaa

idealist, O(n^2).
а тут решение O(n)

Интересно, надо подумать.

@eaa · 25.11.2021, 05:44

стандартная задача на нахождение циклов в перестановке.

@idealist · 25.11.2021, 05:50

Сообщение от eaa

стандартная задача на нахождение циклов в перестановке.

Она, родимая, но я сам сочинял алгоритм, не заглядывал в стандартные.

@eaa · 25.11.2021, 06:25

избавься от этого:

Сообщение от idealist

indexes.remove(i)

@idealist · 25.11.2021, 12:30

Сам что-то не додумался, вычитал вот такой алгоритм, вроде он линейной сложности:

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#===============================================================================
def count_cycles(worlds):
    flags = list('0' * (len(worlds)))
    cycles_counter = 0
    
    for i in range(len(flags)):
        if flags[i] == '0':
            cycles_counter += 1
            w = worlds[i] - 1
 
            while flags[w] != '1':
                flags[w] = '1'
                w = worlds[w] - 1
 
    return cycles_counter
#===============================================================================
def count_portals(worlds):
    res = count_cycles(worlds)
 
    if res == 1:
        res = 0
    return res
#===============================================================================
import random
n = 5
worlds = [1, 2, 3, 4, 5]
random.shuffle(worlds)
print('worlds = ', worlds)
 
print(count_portals(worlds))

Добавлено через 4 часа 25 минут

Сообщение от eaa

избавься от этого:
indexes.remove(i)

Честно говоря, что-то принципиальной разницы между этими алгоритмами я не вижу. Здесь флаги, там у меня такое же количество индексов в качестве флагов. Конечно, установить флаг быстрее, чем удалить индекс, и там у меня для обработки каждого цикла отдельная функция вызывается, а так, мне кажется, алгоритм, в принципе, тот же самый.

@eaa · 25.11.2021, 14:02

idealist, так проверь на n= 10⁵, если не веришь.

Добавлено через 1 минуту
код конечно надо еще "причесать", но ход мыслей правильный.

@idealist · 25.11.2021, 20:00

Сообщение от eaa

idealist, так проверь на n= 105, если не веришь.

Не, я признаю, что предыдущий вариант может быть медленнее, но в чем нелинейность сложности алгоритма?

Добавлено через 5 часов 31 минуту

Сообщение от eaa

код конечно надо еще "причесать"

А в каких местах, интересно узнать ваше мнение.

Новые блоги и статьи Все статьи Все блоги /
http://iceja.net/ математические сервисы iceja 20.01.2026 Обновила свой сайт http:/ / iceja. net/ , приделала Fast Fourier Transform экстраполяцию сигналов. Однако предсказывает далеко не каждый сигнал (см ограничения http:/ / iceja. net/ fourier/ docs ). Также. . .	http://iceja.net/ сервер решения полиномов iceja 18.01.2026 Выкатила http:/ / iceja. net/ сервер решения полиномов (находит действительные корни полиномов методом Штурма). На сайте документация по API, но скажу прямо VPS слабенький и 200 000 полиномов. . .	Расчёт переходных процессов в цепи постоянного тока igorrr37 16.01.2026 / * Дана цепь постоянного тока с R, L, C, k(ключ), U, E, J. Программа составляет систему уравнений по 1 и 2 законам Кирхгофа, решает её и находит: токи, напряжения и их 1 и 2 производные при t = 0;. . .	Восстановить юзерскрипты Greasemonkey из бэкапа браузера damix 15.01.2026 Если восстановить из бэкапа профиль Firefox после переустановки винды, то список юзерскриптов в Greasemonkey будет пустым. Но восстановить их можно так. Для этого понадобится консольная утилита. . .
Сукцессия микоризы: основная теория в виде двух уравнений. anaschu 11.01.2026 https:/ / rutube. ru/ video/ 7a537f578d808e67a3c6fd818a44a5c4/	WordPad для Windows 11 Jel 10.01.2026 WordPad для Windows 11 — это приложение, которое восстанавливает классический текстовый редактор WordPad в операционной системе Windows 11. После того как Microsoft исключила WordPad из. . .	Classic Notepad for Windows 11 Jel 10.01.2026 Old Classic Notepad for Windows 11 Приложение для Windows 11, позволяющее пользователям вернуть классическую версию текстового редактора «Блокнот» из Windows 10. Программа предоставляет более. . .	Почему дизайн решает? Neotwalker 09.01.2026 В современном мире, где конкуренция за внимание потребителя достигла пика, дизайн становится мощным инструментом для успеха бренда. Это не просто красивый внешний вид продукта или сайта — это. . .

@Natasha2005 0 / 0 / 0 Регистрация: 24.11.2021 Сообщений: 2

	Путешествие по мирам 24.11.2021, 14:14. Показов 3976. Ответов 12 Метки c++ std::, java 13, java 8, Pascal (Паскаль), python 3.7.8 (Все метки) Путешественник Мориорти любит путешествовать между мирами. Он знает n миров. Массив a описывает n порталов, с помощью которых он может перемещаться между 2-мя мирами. i-ый портал означает следующее: из i-ого мира существует возможность переместиться в ai-ый мир. Портал перемещает только в одну сторону. Если портал ведет из i-го в j-ый мир, то из j-го в i-ый мир по этому порталу попасть нельзя.В массиве все числа различны. Формально говоря, изначально у Мориорти не существует мира, в который ведет более 1-го портала. У Мориорти могут существовать порталы, которые перемещают в тот же мир в котором они находятся. В массиве все числа различны. Формально говоря, изначально у Мориорти не существует мира, в который ведет более 1-го портала. У Мориорти могут существовать порталы, которые перемещают в тот же мир в котором они находятся. К сожалению, Мориорти из некоторых миров не может попасть в некоторые другие, даже если он будет перемещаться через несколько порталов. Мориорти может построить еще несколько порталов. Но количество порталов ограничено. Помогите Мориорти определить минимальное количество новых порталов, которые ему нужно построить, чтобы попасть из любого мира в любой другой. Например, рассмотрим массив a=[1,4,2,3,5]. На рисунке 1 показаны связи с мирами. На втором рисунке показано возможное решение. Формат ввода В первой строке дано одно число n(1≤n≤105) — количество миров. В следующей строке даны n чисел (1≤ai≤n) — информация об изначальных порталах. Формат вывода Выведите одно число — ответ на задачу Пример 1 Ввод 5 1 2 3 4 5 Вывод 5 Пример 2 Ввод 5 2 3 4 5 1 Вывод 0 Изображения 0

@eaa Status 418 4584 / 2350 / 601 Регистрация: 26.11.2017 Сообщений: 5,262 Записей в блоге: 3
	24.11.2021, 14:59
	Natasha2005, и что конкретно не получается? 0

@eaa Status 418 4584 / 2350 / 601 Регистрация: 26.11.2017 Сообщений: 5,262 Записей в блоге: 3
	25.11.2021, 05:28
	idealist, O(n^2). а тут решение O(n) 0

@eaa Status 418 4584 / 2350 / 601 Регистрация: 26.11.2017 Сообщений: 5,262 Записей в блоге: 3
	25.11.2021, 05:42
	idealist, по одной строке можно определить что это тот же O(n^2) 0

@eaa Status 418 4584 / 2350 / 601 Регистрация: 26.11.2017 Сообщений: 5,262 Записей в блоге: 3
	25.11.2021, 05:44
	стандартная задача на нахождение циклов в перестановке. 0

@eaa Status 418 4584 / 2350 / 601 Регистрация: 26.11.2017 Сообщений: 5,262 Записей в блоге: 3
	25.11.2021, 14:02
	idealist, так проверь на n= 10⁵, если не веришь. Добавлено через 1 минуту код конечно надо еще "причесать", но ход мыслей правильный. 0