Рисунок

@Petya_Rematov · Регистрация: 29.10.2020

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

Задан рисунок, состоящий из пронумерованных точек и линий между ними. Напишите программу, которая скажет можно ли нарисовать этот рисунок (провести ручку по всем точкам и линиям), не отрывая руки и при этом не проводя одну линию дважды?

Входные данные:

Первая строка содержит число N – количество точек (число от 0 до 1000 включительно).

Вторая строка содержит число M – количество линий (число от 0 до 1000 включительно).

Далее идет MM строк, каждая из которых содержит пары номеров точек, соединенных линиями (нумерация точек с 1, между парой точек может быть проведено несколько линий)

Выходные данные:

"Yes", если рисунок можно нарисовать в соответствии с условием

"No", если нет.

Sample Input:

3
2
1 2
2 3
Sample Output:

Yes

@eaa · 09.11.2020, 18:26

что то связанное с четностью вершин графа, я думаю.

@КулХацкеръ · 09.11.2020, 18:43

Python
1
2
3
4
5
6
odd = [0] * (int(input()) + 1)
for i in [0] * int(input()):
    a, b = map(int, input().split())
    odd[a] = 1 - odd[a]
    odd[b] = 1 - odd[b]
print('Yes' if sum(odd) < 3 else 'No')

@Tishran · 10.11.2020, 19:35

КулХацкеръ, стоп, а как, объясни плиз)

@КулХацкеръ · 10.11.2020, 19:46

Так eaa всё объяснил выше. Надо проверить четность степеней вершин графа, если вершин с нечётными степенями не больше двух, то можно обойти граф, проходя по каждому ребру не более одного раза.

@Tishran · 10.11.2020, 19:47

КулХацкеръ, понял, принял, огромнейшее спасибо

@КулХацкеръ · 10.11.2020, 19:48

Почитай в интернете про задачу Эйлера о Кенигсбергских мостах, если интересно.

@Tishran · 10.11.2020, 19:48

КулХацкеръ, уже нашел)

Новые блоги и статьи Все статьи Все блоги /
Установка Qt Creator для C и C++: ставим среду, CMake и MinGW без фреймворка Qt 8Observer8 05.04.2026 Среду разработки Qt Creator можно установить без фреймворка Qt. Есть отдельный репозиторий для этой среды: https:/ / github. com/ qt-creator/ qt-creator, где можно скачать установщик, на вкладке Releases:. . .	AkelPad-скрипты, структуры, и немного лирики.. testuser2 05.04.2026 Такая программа, как AkelPad существует уже давно, и также давно существуют скрипты под нее. Тем не менее, прога живет, периодически что-то не спеша дополняется, улучшается. Что меня в первую очередь. . .	Отображение реквизитов в документе по условию и контроль их заполнения Maks 04.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "ПланированиеСпецтехники", разработанного в конфигурации КА2. Данный документ берёт данные из другого нетипового документа. . .	Фото всей Земли с борта корабля Orion миссии Artemis II kumehtar 04.04.2026 Это первое подобное фото сделанное человеком за 50 лет. Снимок называют новым вариантом легендарной фотографии «The Blue Marble» 1972 года, сделанной с борта корабля «Аполлон-17». Новое фото. . .
Вывод диалогового окна перед закрытием, если документ не проведён Maks 04.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "СписаниеМатериалов", разработанного в конфигурации КА2. Задача: реализовать программный контроль на предмет проведения документа. . .	Программный контроль заполнения реквизитов табличной части документа Maks 02.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "СписаниеМатериалов", разработанного в конфигурации КА2. Задача: 1. Реализовать контроль заполнения реквизита. . .	wmic не является внутренней или внешней командой Maks 02.04.2026 Решение: DISM / Online / Add-Capability / CapabilityName:WMIC~~~~ Отсюда: https:/ / winitpro. ru/ index. php/ 2025/ 02/ 14/ komanda-wmic-ne-naydena/	Программная установка даты и запрет ее изменения Maks 02.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "СписаниеМатериалов", разработанного в конфигурации КА2. Задача: при создании документов установить период списания автоматически. . .

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

	Рисунок 09.11.2020, 18:13. Показов 7688. Ответов 7 Метки python, олимпиада, программирование (Все метки) Задан рисунок, состоящий из пронумерованных точек и линий между ними. Напишите программу, которая скажет можно ли нарисовать этот рисунок (провести ручку по всем точкам и линиям), не отрывая руки и при этом не проводя одну линию дважды? Входные данные: Первая строка содержит число N – количество точек (число от 0 до 1000 включительно). Вторая строка содержит число M – количество линий (число от 0 до 1000 включительно). Далее идет MM строк, каждая из которых содержит пары номеров точек, соединенных линиями (нумерация точек с 1, между парой точек может быть проведено несколько линий) Выходные данные: "Yes", если рисунок можно нарисовать в соответствии с условием "No", если нет. Sample Input: 3 2 1 2 2 3 Sample Output: Yes 0

@eaa Status 418 4584 / 2350 / 601 Регистрация: 26.11.2017 Сообщений: 5,262 Записей в блоге: 3
	09.11.2020, 18:26
	что то связанное с четностью вершин графа, я думаю. 1

@Tishran 0 / 0 / 0 Регистрация: 09.06.2020 Сообщений: 18
	10.11.2020, 19:35
	КулХацкеръ, стоп, а как, объясни плиз) 0

@КулХацкеръ 710 / 356 / 104 Регистрация: 09.02.2018 Сообщений: 805
	10.11.2020, 19:46
	Так eaa всё объяснил выше. Надо проверить четность степеней вершин графа, если вершин с нечётными степенями не больше двух, то можно обойти граф, проходя по каждому ребру не более одного раза. 1

@Tishran 0 / 0 / 0 Регистрация: 09.06.2020 Сообщений: 18
	10.11.2020, 19:47
	КулХацкеръ, понял, принял, огромнейшее спасибо 0

@КулХацкеръ 710 / 356 / 104 Регистрация: 09.02.2018 Сообщений: 805
	10.11.2020, 19:48
	Почитай в интернете про задачу Эйлера о Кенигсбергских мостах, если интересно. 0

@Tishran 0 / 0 / 0 Регистрация: 09.06.2020 Сообщений: 18
	10.11.2020, 19:48
	КулХацкеръ, уже нашел) 0