Построение. Теория графов

@Niggainsoul · Регистрация: 20.10.2018

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

Группа солдат-новобранцев прибыла в армейскую часть N666. После знакомства с прапорщиком стало очевидно, что от работ на кухне по очистке картофеля спасти солдат может только чудо.

Прапорщик, будучи не в состоянии запомнить фамилии, пронумеровал новобранцев от 1 до N. После этого он велел им построиться по росту (начиная с самого высокого). С этой несложной задачей могут справиться даже совсем необученные новобранцы, да вот беда, прапорщик уверил себя, что знает про некоторых солдат, кто из них кого выше, и это далеко не всегда соответствует истине.

После трех дней обучения новобранцам удалось выяснить, что знает (а точнее, думает, что знает) прапорщик. Помогите им, используя эти знания, построиться так, чтобы товарищ прапорщик остался доволен.

Входные данные
Во входном файле INPUT.TXT сначала идут числа N и M (1 ≤ N ≤ 100, 1 ≤ M ≤ 5000) - количество солдат в роте и количество пар солдат, про которых прапорщик знает, кто из них выше. Далее идут эти пары чисел A и B по одной на строке (1 ≤ A,B ≤ N), что означает, что, по мнению прапорщика, солдат A выше, чем B.

Выходные данные
В выходной файл OUTPUT.TXT выведите "Yes" если можно построиться так, чтобы прапорщик остался доволен и "No" если нельзя.

Пример:
INPUT.TXT
5 4
1 3
1 4
4 3
5 2

OUTPUT.TXT
Yes

Байт · 18.03.2019, 15:34

Задача интересная. Но к ней пара вопросов.
- Все ли солдаты разного роста?
- Если прапорщик не знает про данную пару солдат. (а) Он руководствуется объективными критериями? (б) Или ему плевать?
В случае (а) задача довольно трудна. Я даже не знаю, с какой стороны ее укусить. Да и данных для нее маловато.
В случае (б) она сводится к определению наличия циклов в ориентированном графе

@Niggainsoul · 18.03.2019, 18:08 **[ТС]**

Байт, я не знаю( Это всё, что дано.

@aleksey2101 · 24.03.2019, 18:10

Действительно, задача немного непонятная, но в целом алгоритм таков:
(алгоритм топологической сортировки + надо не забыть проверять на ацикличность)
Заведем счетчик времени - переменную, которая в начале работы программы равна 0 и увеличивается на 1 при прохождении программы через некоторую контрольную точку. В качестве контрольной точки выберем точку выхода из процедуры обхода в глубину. Для каждой вершины запомним значение счетчика времени, которое она получила в процессе обхода в глубину, в глобальном массиве. Эти числа позволяют определить, обработку какой вершины поиск в глубину закончил раньше, а какой позже. Их можно назвать "временем выхода" поиска из данной вершины.

Теперь будем запускать модифицированный таким образом поиск в глубину из всех непомеченных вершин, пока таковых не останется. После этого отсортируем вершины в порядке уменьшения времени выхода.

@valen10 · 24.03.2019, 21:13

Сообщение от Байт

Если прапорщик не знает про данную пару солдат

Осмелюсь предположить, что это не важно. Знания прапора не более чем поправки в существующем построении. Главное, чтобы они не были противоречивы, что и требуется проверить. Насчет циклов Вы были правы: нашел задачу на acmp, решение с поиском циклов прошло все тесты.

Кстати, на том сайте есть раздел "Обсуждение", где часто пишут ответы на возникающие в ходе решения вопросы, иногда даже подсказки можно найти (черным - сообщение посетителя, красным - ответ представителя сайта).

До сих пор не пойму, зачем ТС пришел сюда, когда там есть ответ

@aleksey2101 · 25.03.2019, 00:08

В общем, я долго сидел над задачей и никак не мог понять в чем ошибка, ответ прост:
требуется выводить Yes и No, именно таким образом (в отличии от многих задач - где все буквы заглавные)

Возможно, у вас такая же ошибка...

Байт · 25.03.2019, 00:28

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

Осмелюсь предположить, что это не важно. Знания прапора не более чем поправки в существующем построении.

Ага! То есть уже существует совершенно линейный (у всех росты не одинаковые) транзитивный граф, а прапорщик вносит в него свой коррективы.
То есть, есть матрица смежности графа. Прапорщик ее корректирует. Вопрос тот же. Нет ли циклов?
Но у меня ощущение такое, что любое вмешательство в естественный порядок создаст цикл...
Хотя, нет. Если ему подумается, что тот, кто ниже - в самом деле выше, линейный порядок восстановится.

Не по теме:

Имхо, задача вполне социальная:D

@aleksey2101 · 25.03.2019, 12:57

1) Если прапор знает что A > B, то говорим, что в нашем графе существует ребро из A в B .
2) Таким образом, добавляем ребра в граф, т. е. если прапор не знает о некоторых людях, то ребра вообще не создаем.
3) Проверяем есть ли цикл в нашем построенном графе, если есть - то ответ No, иначе - Yes.

@Niggainsoul · 25.03.2019, 13:01 **[ТС]**

aleksey2101, а Вы можете написать код, пожалуйста?

@valen10 · 25.03.2019, 13:32

Не по теме:

Niggainsoul, одно не могу понять: зачем вы вообще беретесь за эти задачи, если сами ничего не делаете. Напишут вам код, вы его отправите, получите плюсик. Смысл?

@_stanislav · 25.03.2019, 13:41

Не по теме:

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

отправите, получите плюсик. Смысл?

я даже не начинаю читать такие объемные посты, где нет ни строчки кода.

Байт · 25.03.2019, 13:46

Не по теме:

Лично меня в данном случае сама бытовая ситуация заинтересовала.:D

@_stanislav · 25.03.2019, 13:53

Не по теме:

Сообщение от Байт

Лично меня в данном случае сама бытовая ситуация заинтересовала

ну ты понятно, ты наверное уже язык наизусть знаешь и стремиться так сказать не к чему

Не по теме:

, а я мозго топливо для изучения языка берегу

@valen10 · 25.03.2019, 14:47

Не по теме:

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

даже не начинаю читать такие объемные посты, где нет ни строчки кода

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

я мозго топливо для изучения языка берегу

Каждому своё. Если вам требуется понимать ЯП на более высоком уровне, то это хорошая практика.

Программистом не работаю, а для своих велосипедов в целом хватает и текущего уровня познаний. Другое дело, научиться решать определенный круг задач.Как озаглавил одну из своих книг известный мэтр программирования Никлаус Вирт: Алгоритмы + Структуры данных = Программы. Считается, что ЯП нужен лишь для конкретной реализации, он не более чем инструмент.

Языки меняются, устаревают, появляются новые. Алгоритмы же более постоянны и применимы с любым ЯП. В одном только универе мне довелось использовать с десяток разных языков от машинных кодов до пролога (жаль, Lisp обошли стороной). Поэтому и нет привязанности к одному из них и желания стать гуру C++.

От таких тем ожидаю лишь, что ТС заинтересован разобраться с решением, а не просто "дайте код". Не хочет сам думать - не надо, зато я решил еще одну интересную задачу =)

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

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

До сих пор не пойму, зачем ТС пришел сюда, когда там есть ответ

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

можете написать код, пожалуйста?

Теперь понял

@_stanislav · 25.03.2019, 15:02

Не по теме:

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

Каждому своё. Если вам требуется понимать ЯП на более высоком уровне, то это хорошая практика.
Программистом не работаю, а для своих велосипедов в целом хватает и текущего уровня познаний. Другое дело, научиться решать определенный круг задач.Как озаглавил одну из своих книг известный мэтр программирования Никлаус Вирт: Алгоритмы + Структуры данных = Программы. Считается, что ЯП нужен лишь для конкретной реализации, он не более чем инструмент.
Языки меняются, устаревают, появляются новые. Алгоритмы же более постоянны и применимы с любым ЯП. В одном только универе мне довелось использовать с десяток разных языков от машинных кодов до пролога (жаль, Lisp обошли стороной). Поэтому и нет привязанности к одному из них и желания стать гуру C++.
От таких тем ожидаю лишь, что ТС заинтересован разобраться с решением, а не просто "дайте код". Не хочет сам думать - не надо, зато я решил еще одну интересную задачу =)

Ок Кеп))) Надеюсь ты это не меня лечил?

@valen10 · 25.03.2019, 15:38

Не по теме:

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

Надеюсь ты это не меня лечил?

Ни в коем случае. Просто объяснил своё странное поведение. Вероятно, это не требовалось. Прошу прощения, если задел ваше ЧСВ, впредь буду осторожнее.

@_stanislav · 25.03.2019, 15:46

Не по теме:

valen10, да ладно тебе, все проще намного, зачем так строго

Не по теме:

или это такой ненавязчивый троллинг, в любом случае не парься

Добавлено через 1 минуту

Не по теме:

valen10, я кстати так и понял, что ты мой фразы в ответ вставил просто для наглядности а не в мой адрес

@aleksey2101 · 25.03.2019, 16:14

Вот код, только разберите сам алгоритм, а не просто код отправляйте.

"Проверка ориентированного графа на ацикличность"

Pascal
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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
var
n,k:integer;
used:array of integer;
m:array of array of integer;  
 
function dfs(v{,par}:integer):boolean;
var
u:integer;
ans:boolean;
begin  
used[v]:=1;
for u:=1 to n do
    begin
    if (m[v,u]=1)and(used[u]=0) then
        begin
        if dfs(u{,v})=false then 
            begin
            dfs:=false;
            exit;
            end;
        end;
        if (m[v,u]=1)and(used[u]=1){and(u<>par)}then
            begin
            dfs:=false;
            exit;            
            end;
    end;
used[v]:=2;   
dfs:=true;
end;
 
var
i,j,l:integer;
res:boolean;
begin
read(n,k);
SetLength(used,n+1);
SetLength(m,n+1);
 
for i:=1 to n do
    begin
    SetLength(m[i],n+1);
    end;
    
for l:=1 to k do
    begin
    read(i,j);
    m[i,j]:=1;
    end;
    
res:=true;
for i:=1 to n do
    if used[i]=0 then
        if dfs(i{,i})=false then 
            begin
            res:=false;
            break;
            end;
        
if res then
    writeln('Yes')
    else
    writeln('No');
end.

@valen10 · 25.03.2019, 16:47

Не по теме:

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

Pascal

Ничего, что тут раздел C++, или для вас нет разницы?

@_stanislav · 25.03.2019, 17:16

Не по теме:

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

Ничего, что тут раздел C++, или для вас нет разницы?

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

Считается, что ЯП нужен лишь для конкретной реализации, он не более чем инструмент.

хихи...

Новые блоги и статьи Все статьи Все блоги /
PhpStorm 2025.3: WSL Terminal всегда стартует в ~ and_y87 14.12.2025 PhpStorm 2025. 3: WSL Terminal всегда стартует в ~ (home), игнорируя директорию проекта Симптом: После обновления до PhpStorm 2025. 3 встроенный терминал WSL открывается в домашней директории. . .	Access VikBal 11.12.2025 Помогите пожалуйста !! Как объединить 2 одинаковые БД Access с разными данными.	Новый ноутбук volvo 07.12.2025 Всем привет. По скидке в "черную пятницу" взял себе новый ноутбук Lenovo ThinkBook 16 G7 на Амазоне: Ryzen 5 7533HS 64 Gb DDR5 1Tb NVMe 16" Full HD Display Win11 Pro	Музыка, написанная Искусственным Интеллектом volvo 04.12.2025 Всем привет. Некоторое время назад меня заинтересовало, что уже умеет ИИ в плане написания музыки для песен, и, собственно, исполнения этих самых песен. Стихов у нас много, уже вышли 4 книги, еще 3. . .	От async/await к виртуальным потокам в Python IndentationError 23.11.2025 Армин Ронахер поставил под сомнение async/ await. Создатель Flask заявляет: цветные функции - провал, виртуальные потоки - решение. Не threading-динозавры, а новое поколение лёгких потоков. Откат?. . .
Поиск "дружественных имён" СОМ портов Argus19 22.11.2025 Поиск "дружественных имён" СОМ портов На странице: https:/ / norseev. ru/ 2018/ 01/ 04/ comportlist_windows/ нашёл схожую тему. Там приведён код на С++, который показывает только имена СОМ портов, типа,. . .	Сколько Государство потратило денег на меня, обеспечивая инсулином. Programma_Boinc 20.11.2025 Сколько Государство потратило денег на меня, обеспечивая инсулином. Вот решила сделать интересный приблизительный подсчет, сколько государство потратило на меня денег на покупку инсулинов. . . .	Ломающие изменения в C#.NStar Alpha Etyuhibosecyu 20.11.2025 Уже можно не только тестировать, но и пользоваться C#. NStar - писать оконные приложения, содержащие надписи, кнопки, текстовые поля и даже изображения, например, моя игра "Три в ряд" написана на этом. . .	Мысли в слух kumehtar 18.11.2025 Кстати, совсем недавно имел разговор на тему медитаций с людьми. И обнаружил, что они вообще не понимают что такое медитация и зачем она нужна. Самые базовые вещи. Для них это - когда просто люди. . .	Создание Single Page Application на фреймах krapotkin 16.11.2025 Статья исключительно для начинающих. Подходы оригинальностью не блещут. В век Веб все очень привыкли к дизайну Single-Page-Application . Быстренько разберем подход "на фреймах". Мы делаем одну. . .

@Niggainsoul 0 / 0 / 0 Регистрация: 20.10.2018 Сообщений: 104

	Построение. Теория графов 18.03.2019, 15:12. Показов 10483. Ответов 22 Метки нет (Все метки) Группа солдат-новобранцев прибыла в армейскую часть N666. После знакомства с прапорщиком стало очевидно, что от работ на кухне по очистке картофеля спасти солдат может только чудо. Прапорщик, будучи не в состоянии запомнить фамилии, пронумеровал новобранцев от 1 до N. После этого он велел им построиться по росту (начиная с самого высокого). С этой несложной задачей могут справиться даже совсем необученные новобранцы, да вот беда, прапорщик уверил себя, что знает про некоторых солдат, кто из них кого выше, и это далеко не всегда соответствует истине. После трех дней обучения новобранцам удалось выяснить, что знает (а точнее, думает, что знает) прапорщик. Помогите им, используя эти знания, построиться так, чтобы товарищ прапорщик остался доволен. Входные данные Во входном файле INPUT.TXT сначала идут числа N и M (1 ≤ N ≤ 100, 1 ≤ M ≤ 5000) - количество солдат в роте и количество пар солдат, про которых прапорщик знает, кто из них выше. Далее идут эти пары чисел A и B по одной на строке (1 ≤ A,B ≤ N), что означает, что, по мнению прапорщика, солдат A выше, чем B. Выходные данные В выходной файл OUTPUT.TXT выведите "Yes" если можно построиться так, чтобы прапорщик остался доволен и "No" если нельзя. Пример: INPUT.TXT 5 4 1 3 1 4 4 3 5 2 OUTPUT.TXT Yes 0

Байт Диссидент 27714 / 17332 / 3810 Регистрация: 24.12.2010 Сообщений: 38,978
	18.03.2019, 15:34
	Задача интересная. Но к ней пара вопросов. - Все ли солдаты разного роста? - Если прапорщик не знает про данную пару солдат. (а) Он руководствуется объективными критериями? (б) Или ему плевать? В случае (а) задача довольно трудна. Я даже не знаю, с какой стороны ее укусить. Да и данных для нее маловато. В случае (б) она сводится к определению наличия циклов в ориентированном графе 1

@Niggainsoul 0 / 0 / 0 Регистрация: 20.10.2018 Сообщений: 104
	18.03.2019, 18:08 [ТС]
	Байт, я не знаю( Это всё, что дано. 0

@aleksey2101 3 / 2 / 1 Регистрация: 06.03.2017 Сообщений: 11
	24.03.2019, 18:10
	Действительно, задача немного непонятная, но в целом алгоритм таков: (алгоритм топологической сортировки + надо не забыть проверять на ацикличность) Заведем счетчик времени - переменную, которая в начале работы программы равна 0 и увеличивается на 1 при прохождении программы через некоторую контрольную точку. В качестве контрольной точки выберем точку выхода из процедуры обхода в глубину. Для каждой вершины запомним значение счетчика времени, которое она получила в процессе обхода в глубину, в глобальном массиве. Эти числа позволяют определить, обработку какой вершины поиск в глубину закончил раньше, а какой позже. Их можно назвать "временем выхода" поиска из данной вершины. Теперь будем запускать модифицированный таким образом поиск в глубину из всех непомеченных вершин, пока таковых не останется. После этого отсортируем вершины в порядке уменьшения времени выхода. 0

@aleksey2101 3 / 2 / 1 Регистрация: 06.03.2017 Сообщений: 11
	25.03.2019, 00:08
	В общем, я долго сидел над задачей и никак не мог понять в чем ошибка, ответ прост: требуется выводить Yes и No, именно таким образом (в отличии от многих задач - где все буквы заглавные) Возможно, у вас такая же ошибка... 0

@aleksey2101 3 / 2 / 1 Регистрация: 06.03.2017 Сообщений: 11
	25.03.2019, 12:57
	1) Если прапор знает что A > B, то говорим, что в нашем графе существует ребро из A в B . 2) Таким образом, добавляем ребра в граф, т. е. если прапор не знает о некоторых людях, то ребра вообще не создаем. 3) Проверяем есть ли цикл в нашем построенном графе, если есть - то ответ No, иначе - Yes. 0

@Niggainsoul 0 / 0 / 0 Регистрация: 20.10.2018 Сообщений: 104
	25.03.2019, 13:01 [ТС]
	aleksey2101, а Вы можете написать код, пожалуйста? 0

@valen10
	25.03.2019, 13:32
	Не по теме: Niggainsoul, одно не могу понять: зачем вы вообще беретесь за эти задачи, если сами ничего не делаете. Напишут вам код, вы его отправите, получите плюсик. Смысл? 0

Байт
	25.03.2019, 13:46
	Не по теме: Лично меня в данном случае сама бытовая ситуация заинтересовала.:D 0

@_stanislav "C with Classes" 2022 / 1404 / 523 Регистрация: 16.08.2014 Сообщений: 5,885 Записей в блоге: 1
	25.03.2019, 15:46
	Не по теме: valen10, да ладно тебе, все проще намного, зачем так строго Не по теме: или это такой ненавязчивый троллинг, в любом случае не парься Добавлено через 1 минуту Не по теме: valen10, я кстати так и понял, что ты мой фразы в ответ вставил просто для наглядности а не в мой адрес 0