0: Так, всем ещё раз привет. Давайте разберём задачу по теории Графов. Вот несколько задач были прям совсем стандартными. Мы их хорошо обсудили на лекции. Это, допустим, задача c4 связанность просто

1: Нужно было проверить неориентированный граф на связанность. То есть мы должны были запустить дфс от любой вершины, допустим, от 1, а потом посмотреть на массив вис. Он должен был заполнен, он должен был быть заполнен целиком, единичками, если есть

2: Хотя бы 1 0. Значит, какая-то вершина у нас не вошла в компоненту связанности ту же самую, что единица. Значит, у нас как минимум 2 компоненты связанности. И граф не связанный. Если все вершины посещены, то есть помечены единичками, значит, компонента связанности. 1 вот.

3: Есть ли вопросы у кого-то по c4?

4: Хорошо, вроде бы вопросов нет, задача d4 была довольно похожей, но в ней нужно было уже выделить все компоненты связанности, посчитать их и вывести их содержимое. Точнее, нужно было как-то.

5: Скажем так, пронумеровать вершины по тем компонентам связанности, куда они входят, нумерация была на самом деле не такой строгой, то есть самое главное, чтобы все вершины, которые входили в 1 и ту же компоненту связанности, имели один и тот же номер в ответе.

6: Вот, ну что можно было сделать? Можно было поддерживать какой-то так, сдача. D4. Можно было поддерживать какой-то глобальный счётчик, то есть что-то в духе. Номер компоненты, номер текущей компоненты, который начинался бы с единицы в мейне.

7: Запустить серию дфов вот такую вот

8: Запускаем дфс, просто нужно было в дфс сделать ещё такую модификацию, что как только мы заходим в вершину какую-то, мы должны в каком-то ееще массиве номер компонента этой вершины.

9: Поставить равным текущему номеру, то есть просто использовать вот этот вот глобальный счётчик.

10: Вот, соответственно, когда у нас дфс завершается очередной, мы просто вот этот глобальный счётчик должны были увеличить на 1.

11: Ну и в принципе все. То есть запускаем дфс внутри дфс всем вершинам компоненты, а дфс обходит именно компоненту. Ставим значение 1 и того же, ну по сути, значение 1 и той же переменной в их номер компоненты.

12: А после завершения дфс счётчик, точнее номер текущей компоненты увеличиваем на 1. Можно это делать и предварительно перед дфсо разницы никакой не будет. Так, вопросы по задаче д. 4. А, ну да, кстати, граф.

13: Тоже не ориентированы. Поэтому мы ищем компоненты. Вопрос по задаче д. 4.

14: Кажется, вопросов нет. Хорошо. Так, задача б, 4. Пошаговый обход графа, по сути, нам тоже, скажем так, don какой-то неориентированный граф. Вот.

15: Да, то есть нам говорят, что ребро между вершиной у, и в это просто как бы ребро между ними, то есть не в какую-то сторону. Вот, что нам нужно было вывести, нужно было вывести какую-то последовательность.

16: Вершин. Вот, скажем так.

17: Но именно как как будто бы можно сказать, как отдельные запуски, что ли. То есть давайте это формализуем так же, как это написано в задаче. То есть пошаговым обходом они называли вот такую вот последовательность вершин.

18: Вот, и были несколько условий, то есть

19: Было совпадение 1 и последней вершины из номера. Ну то есть, причём, да, давайте, давайте скажем так, пошаговый обход именно как бы был для каждой вершины, можно сказать, или для какой-то конкретной вершины, то есть пошаговый обход вершины в это вот такая вот последовательно

20: Номеров вершин такая, что 1, последний номер это, по сути, самая вершина в вот, и, скажем так, в этом обходе.

21: Ну, каждая вершина, которая достижима из в, она должна упоминаться хотя бы 1 раз. То есть те вершины, до которых есть путь из в, мы их должны были все хотя бы раз в этой последовательности выписать. Вот.

22: Причём ещё было важно, чтобы между любыми 2 выписанными нами вершинами было ребро.

23: Вот было ребро, да, то есть это чем-то походит, да, и мы, видимо, должны были вывести любой пошаговый обход от какой-то вершины, то есть номер вершины, от которой мы должны были запустить обход.

24: Нам тоже, кажется, задавали. Вот, ну, давайте подумаем то есть это походит на дфс, то есть берём вершину в просто от неё, казалось бы, запускаемся, доходим до всех достижимых, просто все куда заходим, дсом выписываем.

25: Вот, но есть на самом деле небольшая проблема, с чем она связана? Представим, что мы начинаем с вершины в, идём в какую-нибудь вершину, допустим, 1, 2, 3, 4, как это у нас будет происходить? Ну, мы, собственно, будем выписывать. То есть, если мы будем выписывать каждую вершин,

26: В который мы заходим дфс мы выпишем в 1, 2, 3, 4. Вот. И тут важный момент на четвёрке мы упираемся в тупик и рекурсивно как бы снимаем этот вызов, возвращаемся к тройке. Тройка идёт к следующему соседу. Допустим, это пятёрка.

27: И тогда в дфс мы после четвёрки выпишем пятёрку, но это проблема, потому что мы на самом деле нарушаем свойства того, что у нас любые 2 соседние выписанные вершины должны быть, ну, соседними в ответе должны быть также соседними в графе, то есть есл.

28: Я выписываю 4, а потом 5. Между ними должно быть ребро, а у нас его нет между 4 и 5. Нет ребра. Вот. Поэтому нельзя было вот так вот просто перепрыгивать, как это обычно делает дфс. Ну, на самом деле, то есть дфс, как бы он, конечно же, далеко не двигается, он

29: Когда идёт или по ребру вперёд, или просто рекурсивно откатывается по ребру назад. Вот, ну в том и проблема, что мы, что дфсс может несколько раз откатиться куда-то далеко, уйти от вершины, даже возможно вот так и потом зайти в какую-то другую

30: Ну, поэтому, собственно, и нужно было учитывать не только заходы в вершины, но и выходы из них, то есть, и откаты назад тоже. Поэтому можно было поступить так, запустить дфс от вершины в вот он, условный дфс.

31: Просто нужно было выписывать вершину в каждый раз, когда мы в неё заходим. Вот тут мы обходим соседей там и каждый раз, когда мы из вершины выходим. Вот, ну как это работает, мы заходим в вершину, в выписываем там в 1, 2

32: 3, 4. Потом из четвёрки мы выходим, потому что из неё больше некуда идти, и снова выписываем четвёрку. Вот.

33: Да, так причём?

34: Ну, можно сказать, что у нас тут не существует, конечно, ребра между четвёркой и четвёркой. В принципе, мы могли даже тогда так не делать. Да, извиняюсь, немного плохой вариант, потому что вроде мы не могли. Все-таки, я думаю, здесь вы

35: Таким образом, лучше тогда лучше тогда поступить немножко по другому. В чем у нас на самом деле проблема. Проблема в том, что вот у нас у тройки есть 2 ребёнка, 4 и 5. Ну мы там когда-то приходим в тройку, выписываем её, потом мы

36: Выписываем четвёрку и потом сразу пятёрку выписывать нельзя. То есть нужно как бы переход от четвёрки к пятёрке осуществить по тройке. Это на самом деле так и происходит. Четвёрка откатывается в тройку, тройка идёт в пятёрку. Поэтому каждый раз, когда мы возвращаемся в родительскую вершину, все-таки надо выписывать именно

37: Родительскую вершину. Вот. Ну, неудобно передавать, родительскую вершину лучше сделать так каждый раз, когда мы сходили в какого-то 1 сына, мы же рано или поздно в него вернёмся обратно в нашу вершину. И когда мы вернёмся обратно, после этого лучше всего нашу вершину снова выписать.

38: Прежде чем идти какого-то другого сына. Вот исключение, наверное, если, наверное, как бы на последнем шаге это можно было учитывать. То есть, наверное, когда мы обошли всех сыновей повторно на выходе нашу вершину.

39: Писывать все-таки не стоило. Ну это можно было как-то обыграть. Вот. То есть что мы делаем, мы идём по всем детям.

40: Вот, то есть, что мы делаем, мы там проверяем, если ребёнок не посещён.

41: Мы заходим фссом вот в эту вершину ребёнка. Вот, да, и на самом деле после этого ещё раз

42: Вот именно здесь, в этом же Ифе, выписываем нашу вершину в то есть мы пойдём в ребёнка, как-то его обойдём, рекурсивно откатимся вершину в и её выпишем, чтоб, когда мы пойдём в следующего ребёнка, нам уже знать. Ну, собственно, нам уже

43: Как-то понимать, что прежде чем пойти в следующего ребёнка, мы должны как бы из вершины ту все-таки откатиться в обратно, чтобы перейти к какому-то там to odin именно через вершину в в последовательности. Вот, ну, можно было

44: Не принтить, а просто собирать ответ куда-то. Да, у нас каждая вершина бы, скорее всего, продублировалась. Точнее, не каждая вершина, а вершина, из которых мы никуда не будем ходить, у которых, по сути, не останется свободных соседей. Мы их, кажется.

45: А, нет, мы их тоже не выпишем 2 раза. То есть все хорошо. Каждый раз, когда после нашей вершины возникает поход в какого-то соседа, мы запускаемся от него, он там все от себя выписывает. Возвращаемся обратно в в. И снова её выписываем.

46: Чтобы как бы это дело замкнуть. Вот, то есть вот у нас вершина в, мы идём в ту, он там как-то обрабатывает свою часть графа, все это дело выписывает. Мы знаем, что обход вершины, ту, как бы

47: Курсивно тоже заканчивается на two, потом мы откатываемся сюда, выписываем в и идём уже в следующего ребёнка вот он мы знаем, что он там выпишет себя, то есть все будет хорошо получается, тогда на самом деле мы выписываем вершину каждый раз, когда заходим в неё и

48: Каждый раз, когда мы приходим в нашу вершину обратно после захода в какого-то ребёнка, вот это вот задача b4. Так, вопросы по задаче b4.

49: Угу. Вопросов, кажется, нет.

50: Так, тогда задача e4 в задаче e4 нам давали определение, нам говорили, что неориентированный граф называется деревом, если он связанный и в нём нет циклов. Вот, то есть, ну, или другими словами,

51: Между любой парой вершин существует Ровно 1 единственный путь.

52: Ну, допустим, такое дерево.

53: То есть нам нужно было, если говорить по определению, нам нужно было проверить неориентированный граф на связанность. Мы это умеем из задачи c4 и проверить, что в нём нет циклов. В принципе, можно было проверять, что нет циклов. Мы говорили, что цикл это когда

54: Мы возвращаемся в посещённую вершину в неориентированном графе. Ну, кроме того, что как бы вершина 3 смотрит на двойку, из которой она пришла, но это не считается циклом. Вот. Но это довольно сложно, если так посмотреть, на самом деле можно заметить, что в дереве

55: Из n вершин Ровно н - 1 ребро всегда дерево, это связано, вот поэтому всегда.

56: Потому что на самом деле, можно сказать, у каждой вершины есть ребро в родителя какого-то предшественника, в какую-то более главную вершину, кроме Корня, кроме вот такой можно назвать вершины, от которой мы запускаем дфс.

57: То есть, если мы запустим дфс от любой вершины дерева, мы придём до всех остальных. Вот у каждой вершины будет предшественник, кроме самой 1. Ну так это довольно конструктивно. Можно там доказать по индукции. Вот, то есть

58: Дерева всегда есть листовая вершина, которая, у которой всего Ровно 1 сосед. Скажем, если такой вершины нет, у нас был бы цикл, иначе вот если мы эту, этот лист уберём по индукции, предполагаем, что здесь

59: Рёбер на 1 меньше, чем вершин. Добавляем 1 ребро, 1 вершину и все сохраняется. Поэтому достаточно было проверить, что на самом деле граф просто связный.

60: Вот. И количество рёбер равно количеству вершин - 1. Вот так можно проверять на дерево.

61: То есть вот эти вот 3 пункта, на самом деле, связанный рёбер авно н - 1 и нет циклов, это довольно забавное свойство. Можно взять любые 2 из них. И 3 будет выполняться автоматически. То есть, если граф связный, и в нём, н. Минус,

62: 1 ребро, то нет циклов. Если в графе н - 1 ребро, и нет циклов, то он связанный. Ну и если там граф связный, в нём нет циклов, то в нём, н - 1 ребро, то есть любые 2 берём. 3 из них автоматически следует. Так?

63: Есть ли вопросы по задаче e4?

64: Так, хорошо, кажется, вопросов нет. Задача g4 была построить топологическую сортировку, либо понять, что её нет. Ну, мы, в принципе, про это тоже на лекции подробно поговорили. То есть мы про

65: Просто сортируем вершины по времени выхода из дфс. Вот проверять можно вот этим алгоритмом, который мы писали на проверку циклов. Либо, насколько я понимаю, можно было просто, ну вот у нас там более ранние вершины, там более поздние, допусти.

66: Ну, там более верхние, более нижние. Вот можно было, кажется, построить топологическую сортировку и позапускать дфс серию дфсо, то есть не очищая вис вот так вот справа налево. Главное, чтоб мы из поздних вершин не пришл.

67: Ранее, кажется, можно было проверить так, если кто-то по другому проверял наличие циклов или там отсутствие циклов в задачах g4, можете написать свои варианты в чате довольно интересно. Ну, трехцветная раскраска точно.

68: Работала.

69: Вот. Ну и если вдруг есть вопросы по задаче g4, тоже их жду.

70: Красит ребра. Угу. Понятно.

71: Ну и, собственно, задача h4 была как раз-таки на проверку цикла, мы про это тоже говорили, это делается. То есть там граф был ориентированным, вот.

72: Поэтому работала обычная трехцветная раскраска, о которой мы говорили, так что если у кого-то вдруг в h4 что-то не получилось или не совсем понятна была трехцветная раскраска, в какой-то момент тоже можем обсудить, задавайте вопросы.

73: То есть там тоже ничего необычного, просто выполнить стандартный алгоритм проверки.

74: Хорошо, вопросов вроде нет. Так, тогда, я думаю, можно поговорить про задачу. F4. Вроде все простое, стандартное. Более или менее разобрали. Так, подробнее про трехцветную раскраску. А есть?

75: Какой-то конкретный вопрос.

76: Ну, я могу вкратце повторить, что происходило в трехцветной раскраске. То есть мы условно в дфс, когда заходили в вершину, мы её красили в серый цвет. Вот.

77: Поэтому, допустим, если мы запускались отсюда и у нас шла какая-то цепочка, она была покрашена серым.

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

79: Что вершина ведёт в чёрную, то есть двойку. Ну то есть вершина, из которой мы уже вышли. Фсм это не цикл, потому что раз мы из той вершины уже вышли из вот этой, из неё не было пути до сюда. Ну раз вот находясь в этой вершине, в текущем

80: Мы обнаружили какую-то уже посещённую либо предыдущим фссом, либо текущим. Значит мы из этой вершины уже вышли, которая у нас там двойка. Вот. Но по какой-то причине до единицы мы из неё не шли. Раз сейчас мы смотрим на единицу

81: Значит, из двойки в единицу пути нет, значит, это не цикл. Ну вот, ну и каждый раз, когда мы видели там белую вершину нулевую, мы в неё шли и красили единицей. Вот. А когда мы, допустим, вот упёрлись в тупик, мы просто берём вершину, перекрашиваем двойку и выходим, откатываемся.

82: Соответственно, если кто то когда-то там увидит ребро сюда, в дальнейшем это уже не будет считаться циклом.

83: Вот так. Ещё вопросы. Может быть, по раскраске?

84: Хорошо, вроде вопросов нет. Так, тогда задача f4 про бусинки. Так что-то пишут, какие именно вершины выводить. Это в какой задаче? В там, где цикл, а там его надо было вывести, да?

85: Ну, смотрите, соответственно, нужно было посмотреть на момент нахождения цикла.

86: То есть вот, допустим, мы замыкаемся, ну давайте побольше немного.

87: Когда мы замыкаемся, мы видим, на какой вершине мы замыкаемся. То есть, допустим, из вершины в 1 мы поняли, что, попадая в вершину, в 2, мы образуем цикл типа все эти вершины серые, соответственно, что является тогда циклом, ну, циклом является

88: Путь от в 2 до в 1 вот, вот такой вот путь, ну, вместе с этим ребром, ну, там цикл, это как бы вершина. Ну что это за вершины? Это все вершины между, собственно, в 2 и в 1 можно

89: Было просто заходя в дфс, вершину, в которую мы заходим складывать в какой-то стек.

90: Вот, а когда мы выходим из дфс, можно было эту вершину оттуда удалять.

91: С вершин, ну просто удалять вершину, с вершины удалять вершину со стека. Просто вот таким образом в стеке у нас бы всегда в момент захода в какую-то вершину хранились бы, хранилась бы вот эта текущая цепочка целиком. Вот

92: А когда мы 1 раз находим цикл, можно просто сказать, что все дальше никуда, никаких ответвлений не надо. Надо просто запомнить, что цикл это начинается в вершине в 2. Соответственно, из в 1 в 2 мы уже не идём, конечно, потому что уже там были, были, поэтому мы просто начинаем выписывать вершины с конца.

93: Стека, то есть в 1 вот эту вот вершину и доходим до в 2, когда мы доходим до в 2, нужно прекратить выписывать вершины из стека, просто завершить целиком алгоритм. Вот как-то так. То есть, да, все можно было поддерживать стеком.

94: Может быть есть какие-то ещё другие техники, но такая, наверное, самая простая.

95: Так, ещё вопросы?

96: Так, ещё немного вопросы по раскраске жду и если нет, переходим к бусинкам.

97: Так, ну хорошо, задача ф, 4. Там было несколько бусинок, их как-то просто выложили на пол. Ну, они были пронумерованы, конечно. Вот. И как-то произвольно посоединяли, причём говорят, что замкнутых фигур

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

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

100: И то, что просто у каждой вершины есть сосед, кто сдавал задачу. F4, пожалуйста, напишите в чате, был, было ли вот это вот был ли граф f4 связан

101: Мне кажется, судя по этому предложению, должно было быть несколько не связанности, но в любой из них не должно было быть циклов. То есть бусинка соединена с какой-либо другой. Видимо, имеется ввиду, что, как бы это сказать.

102: У каждой бусинки есть сосед, хотя не очень то понятно, зачем это нужно. Вот если все же там было, был связанный граф, то, пожалуйста, напишите. Вот опять же, это не сильно меняет задачу. Что нам нужно было сделать? Нам нужно было

103: Определить количество максимальное количество последовательно соединённых бусинок. Вот.

104: Ну то есть, что-то вроде длиннейшего пути, ну причём пути, которые не ходят там вперёд, назад, вот если фигура была связанной, то это, получается, было дерево, если все же эти, то есть, если было

105: Несколько компонент связанности, то, ну мы просто могли каждый обрабатывать отдельно. Вот это тоже не очень сложно, просто на каждый у нас уйдёт отдельный дфс. Вот. То есть нам нужно было, видимо, найти длину самой длинной цепочки.

106: Бусинок. Вот.

107: Ну, в примерах, там, в принципе, все понятно, там такие длинные вытянутые линии. Вот.

108: Получается как-то так. Причём длину, видимо, в количестве бусинок. Ну можно и в количестве рёбер. Если у нас в пути несколько рёбер, допустим, 3, то вершин на 1 больше. Вот вообще такая.

109: Штука в принципе называется диаметром вот диаметром дерева. То есть у нас это получается вот максимум по всем каким-то расстояниям ну то есть длина пути, можно его её назвать расстояние между вершинами. Так, у нас

110: Будет обозначаться расстояние в количестве рёбер, ну или длина пути. То есть сколько рёбер нужно пройти, чтобы попасть из вершины у в вершину, в вот, ну и, собственно, диаметром называется максимальное такое расстояние по всем.

111: Вершина ув. Ну с учётом, что мы в пути не ходим туда, обратно, мы просто вот прямо идём по направлению к цели. Вот туда сюда мы не ходим. Вот как можно искать диаметры в дереве, вот эти вот максимальные

112: Состояние в дереве. Ну, собственно.

113: Давайте немного подумаем. То есть какие, интересно, 2 вершины наиболее удалены друг от друга в дереве. Ну, давайте нарисуем дерево и попробуем подумать, что, что это за вершины, хотя бы какие у них там свойства.

114: Вот утверждается, что 2 самые удалённые друг от друга вершины, они являются листьями, то есть это 2 такие вершины, у которых Ровно 1 сосед.

115: Вот, ну, действительно, если мы выберем какие-то вершины, 1 из которых не лист, ну, то есть я вот, допустим, выбрал какой-то путь вот такой в дереве, и, допустим, вот эта вершина не лист, ну тогда, значит, у неё есть

116: Кроме вот этого вот соседа ещё хотя бы 1, так сказать, внизу мы можем перейти к нему и это расстояние только увеличится поэтому а раз увеличится, значит вот это вот расстояние не могло быть максимальным. Вот поэтому на самом деле обе вершины

117: Концах диаметра на концах самого длинного расстояния должны быть листами. Вот, ну что на самом деле это за такие листы? Вот действительно я тут нарисовал. Так получилось, что у нас, наверное, самое длинное расстояние, оно, конечно, возможно, будет как-то

118: Идти, скажем так, от Корня до листа, но корень в случае, если корень сам является листом, скорее всего, у нас будут 2 листа, ну у которых есть какой-то, скажем так, общий предок. Вот. То есть, допустим, у этой вершины, у этой вершины

119: Общий предок вот здесь вот, ну, корень тоже общий предок, ну, будем говорить такой самый нижний общий предок, наименьший общий предок. Вот. То есть есть такая развилка, где впервые мы сначала мы шли 1 путём, а потом мы

120: До 2 целевых вершин пойдём уже 2 разными путями. Вот нам бы хотелось найти, видимо, вершину, у которой, скажем так, есть какие-то 2 глубокие листа в разных её 2, скажем, сыновьях или

121: Вот в таких вот вот поэтому, в принципе, вообще нам стоит брать, кажется, вершины, у которых глубина как можно больше, то есть которые как можно глубже дальше от Корня лежат. Если мы берём не такие вершины, мы

122: Можем всегда, допустим, если ни 1, ни 1 из этих вершин, допустим, не является вообще самой глубокой, вот относительно вот этой по расстоянию мы можем взять какую-то, которая глубже и лишь

123: Улучшить расстояние. Вот, поэтому, кажется нам нужно брать все-таки самые глубокие вершины. Вот, ну, опять же, при этом у нас вершин там довольно много в этом дереве. Ну, хотя, хотя в этом вот конкретно в f4 не очень

124: Много. Поэтому, в принципе, можно было сделать, что можно было пытаться запустить дфс от каждой вершины, да, и вообще говоря, то есть, ну нам же нужно найти такие 2 вершины уив, которые наиболее удалены. Можно было вообще пытаться запустить дфс.

125: Любой вершины, то есть любую взять за начальную, за корень, от неё запускаться и просто считать расстояние. На самом деле, как у нас считается расстояние до фссом в дереве. Ну, можно сказать, вот здесь расстояние 0, то есть от этой вершины 1 до самой себя дальше.

126: Расстояние 1, можно сказать, это глубина 1. То есть это как бы непосредственные соседи. Дальше расстояние 2, ну и так далее. То есть мы могли в дфс помимо вершины поддерживать ещё какой-то счётчик, который

127: Мы называем глубиной. Начинается он с нуля, то есть запускаем от единицы там или от какой-то вершины с нулём. И когда мы вызываем дфс от какого-то ребёнка нашей вершины, мы его называем ту, мы просто глубину ему передаём на

128: 1 больше. То есть мы углубляемся в дерево. Таким образом, можно было у нас там, н было не более 2500. Кажется, можно было от каждой вершины позапускать я посмотреть, посчитать от неё глубины расстояния до всех остальных и, в общем то,

129: Буквально мы бы за н, в квадрате это все и решили, вот буквально за н, в квадрате, мы бы это все и решили. Можно чуть быстрее. Ну, точнее, значительно быстрее. Наверное, вот можно сразу запуститься от любой

130: Изначально абсолютно от любой и найти от неё самый, то есть туда запуститься, посчитать глубины и взять самый глубокий лист, ну, самую глубокую вершину, то есть вершину, которая дальше всех от нашей, мы её назовём. М, а уже потом

131: От этой вершины м запуститься и найти от неё самую глубокую. Вот и утверждается, что, допустим, m 1 утверждается, что вот это вот и есть ответ. 2 самые удалённые вершины, ну и вот расстояние между ними самое максимальное ну, мы примерно это доказали почему?

132: Нам нужен лист, конечно, среди всех листов нам нужен самый глубокий, ну потому что не самые глубокие брать неоптимально. Вот получается как-то так.

133: Вот, то есть вот мы находим самую глубокую вершину, потом мы запустимся от неё фо, она там как то куда-то пойдёт, насколько то вверх, скажем, а потом куда-то отклонится и придёт в другую вершину m 1. Вот.

134: Если бы мы запустились от какой-то менее глубокой вершины, то есть как-нибудь, не знаю, вот так, какой-то другой, скажем, ну назовём её, допустим, п. У нас бы уже не получилось.

135: Такой истории, то есть, либо мы шли бы сюда же, но это было бы короче, либо мы шли бы куда-то в другую ветку. Вот. Причём не в эту, иначе опять же, мы все равно затронем вершину м, она у себя там самая глубокая ветк.

136: Если бы мы пошли куда-то вообще в постороннее место. Опять же, если это был бы очень длинный путь, но тогда, м, в любом случае лучше, чем п в такой ситуации. Так что мы, по сути, запускаем ещё раз дфс от единицы, находим самую глубокую вершину м, потом запускаем дфс от

137: Эмки и ищем от неё самую удалённую вершину по глубине. Ну и вот ответ это м, 1 м 2, извиняюсь. М м 1. Вот так можно решать за линию. Вот если да, если

138: У нас деревьев несколько, мы компонент связанности. Несколько точнее, мы запускаемся от каждой независимо. То есть просто цикл с дсами. Вот есть ли у кого-то вопросы по задаче вот, f4.

139: Может быть какой-то момент повторить или

140: Какое-то другое решение, может быть, делали?

141: Так, хорошо, вроде вопросов нет, давайте поговорим тогда про i 4 это задача города 1 вот в задаче y 1 тоже было ой, извиняюсь, задача i 4 тоже было дерево. Вот, но оно там уже было довольно большое.

142: Было 100000 вершин, ну или не более 100000. Во всяком случае, вот тут было понятие удалённости, то есть удалённости какой-то вершины, вот удалённость.

143: Вершины в будем её называть вот так. Удалённостью вершины в. Называлось максимальное расстояние от вершины в до какой-либо другой.

144: То есть по всем у всем вот удалённость вершины это максимум из расстояний от него до какой-то другой вершины. Вот нам нужно было найти города.

145: У которых удалённость минимальна. Причём все такие города, вот давайте называть вот города с таким города, с минимальной удалённостью центральными. Ну почему центральными, на самом деле, ну потому что города, от которых максимальная

146: Расстояние наименьшее, они, как бы, можно сказать, в каком-то смысле находятся в центре. То есть им до всех близко. Вот им до всех близко, можно сказать, остальным друг до друга. Дальше может быть, а вот им до всех близко, условно. Вот.

147: Ну и множество таких центральных вершин можно называть центром. Вот как нам найти вот этот вот центр дерева. На самом деле в предыдущей задаче мы говорили про диаметр. Давайте посмотрим на диаметр. Диаметр это самое длинное расстояние в дереве между какими-либо 2

148: Давайте возьмём и нарисуем диаметр.

149: То есть предположим, что вот оно, самое длинное расстояние.

150: Ну вот на нём, допустим, 7 вершин лежит. Вот тогда, кажется, у нас вот эта вот минимальная удалённость, ну то есть, как сказать, да, минимальная удалённость вершины как-то связана с диаметром там, вот он.

151: У нас центральная вершина, возможно, у нас от этих вершин ещё какие-то отходят другие, но не сильно далеко, потому что это и так максимальное расстояние.

152: Ну, кажется, в принципе, что вот этот центр, он, в принципе, есть центр, он есть как раз-таки вершина с наименьшей удалённостью других. Вот.

153: Почему на самом деле так? На самом деле ни 1 из этих вершин не является центральной, не является минимально удалённой, вот не является минимально удалённой, потому что всем этим вершинам на са

154: На самом деле, на 1, дальше идти до вот этой, то есть центр, мы его назовём ц, ему досюда, кажется, вот, допустим, 3 шага. И это у него, в принципе, максимальная удалённость. Вот, то есть у нас

155: У нас не может быть на самом деле, если это диаметр, то от центра не может быть удалённость более чем на 3 ребра. Ну, если бы была такая удалённость куда-то более чем на 3 ребра, допустим, вот так на 4, тогда мы бы могли диаметр удлинить, а диаметр то у нас

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

157: Точно выигрывает. Вот. Да, кстати, от центра ещё могут исходить ребра. Вот что можно сказать про те вершины, которые как бы, висят на вот этих вот, не знаю, стрелках, диа.

158: С ними все ещё хуже. Вот, потому что если у нас какая-то вершина как бы висит на, не знаю, ну зацеплена за вершину на диаметре, то она ничуть не лучше, ей ещё дольше добираться до другого конца диаметра поэтому

159: Получается плохо. То есть настоящим центром считается только вот Середина диаметра. Что если у нас диаметр, допустим, чётной длины 6 вершин, скажем, ну тогда можно считать обе вот эти вершины центром те же самые

160: Рассуждения. Вот итого, видимо, вот эта вот самая минимальная удалённость, это длина диаметра. Будем называть её д большое, поделить пополам с округлением вверх. Вот.

161: Только так, извиняюсь сейчас, смотря что считать длиной диаметра. Если длина диаметра это количество рёбер, то да, в верхнем случае 6 рёбер делим на 2 удалённость максимальная, точнее, минимальная удалённость 3 в нижнем.

162: Случае 5 рёбер, удалённость минимальная, все равно 3. Вот можно было как-то так действовать. Ну и соответственно сами центральные вершины это либо 1 средняя на диаметре, либо если диаметр содержит Нечет.

163: Количество рёбер, соответственно, чётное количество вершин, то центральных вершины 2, ну, более быть не может. Вот. Ну, и поскольку у нас там 1 связанное дерево, то про компоненты связанности думать не приходится. Вот, в принципе, такая идея в задаче и

164: 4, то есть находим диаметры, как мы там говорили, дфс с глубинами, а уже потом от него работаем. Вот, то есть нас там будет интересовать путь от м до м 1, и все на этом пути нужно будет как-то вершины с этого пути вывести.

165: Ну, на самом деле, это не сложно. Мы запускаемся, м, и просто там у нас дфс, если мы понимаем, что какая-то ветка не придёт в м 1, мы её просто игнорируем, это можно так или иначе сделать какой-то флажок, возвращать дфсо, если какая-то ветка приходит в м 1, ну да.

166: А мы её, мы вершину с неё выписываем вот так есть ли у кого-то вопросы по задаче y 4, может быть, какие-то предложения или как-то по другому решали, более интересно.

167: Ну, в плане не так, не таким методом.

168: Так, ещё немного жду вопросов по ai 4.

169: Хорошо. И осталась у нас ещё задача. A4 самая 1. Так, или есть вопросы? Уже была задача найти. Не все, не листья. Нет, нет, не совсем.

170: Если вы про задачу a4, то задача была найти вершину с наименьшей удалённостью, то есть с наименьшим Макс расстоянием до других. Вот.

171: Соответственно, мы говорим, что да, ну там конкретно сейчас скажу, что нужно было ввести саму удалённость.

172: И список городов, для которого она количество и список городов, для которого она достигается. То есть нам нужно было найти 1, ну, либо там 2 серединки диаметра, смотря сколько их и длину диаметра.

173: То есть на самом деле вот эта вот минимальная удалённость связана с максимальной

174: Можно было решать как-то через листья, да, там есть какой-то метод, что если мы все листья уберём в дереве, то центр сохранится.

175: Ну, мне кажется, через диаметр намного проще. Тем более это полезно для задачи. Ф, вот ещё вопросы.

176: Так, хорошо, давайте поговорим про, a4. Задача про лабиринт, она вообще не на тему сегодняшней лекции, конечно, но давайте посмотрим, там было какое-то поле, м, причём оба измерения были вроде

177: До 1000, можно сказать, такой лабиринт на квадратной сетке, вот в чем заключалась его лабиринтность, в том, что некоторые клетки у нас были как бы запрещены, там были повалены деревья.

178: Вот, а некоторые клетки были свободны. То есть нам нужно было как-то вот

179: Так, прошу прощения, здесь, скорее всего, есть линия, да?

180: И нам нужно было, в общем то, находясь в какой-то свободной клетке, ну не поваленной деревьями, добраться до какой-то другой клетки, свободной, тоже не поваленной деревьями. Вот, ну, как-то тут все было закрашено, не знаю, допустим, вот как-то та

181: То есть закрашенные клетки нам запрещены для посещения.

182: Вот мы их должны обходить там и так далее.

183: Вот, допустим, мы где-то здесь находимся, а нам нужно попасть сюда. Либо, кстати, понять, что мы не можем попасть на нужную клетку. Такое тоже могло в теории быть. Вот расстояние, причём до нужной клетки нужно было найт

184: Именно кратчайшее ходить по этому лабиринту мы могли там вверх вниз, влево, вправо, вот вроде бы по диагонали не могли.

185: Ну, кстати, как-то это в условии не очень то и сказано.

186: Да, ну, я так понимаю, могли ходить только верхние, слева вправо, если мы вдруг могли ходить по диагонали, пожалуйста, напишите в чате. Вот. Ну, это уже ближе к алгоритмам поиска кратчайшего пути. Вот.

187: Только верх, низ, а лево, право, можно было.

188: Только через сторону. Ну да, судя по тестам, только через сторону. Ну то есть вот у нас есть клетка, мы можем ходить вот так. Ну понятно, мы не можем ходить в запрещённые, закрашенные. Что тут можно было делать? Ну, то есть, когда он, ну, причём у нас

189: Кратчайшее расстояние. У нас каждый переход весит как бы единицу, можно сказать, или стоит единицу. Вот в таких графах можно пользоваться вот похожим алгоритмом, подобным алгоритмом. То есть мы начинаем с какой-то вершины стартовой оче,

190: Видно, что расстояние от неё до неё самой это 0. Вот. А потом, подобно тому, как мы обходили деревья в глубину, у нас есть соседи этой вершины. Вот. Ну, кстати, это и на ориентированных графах тоже работает. Соседи этой вершины.

191: Ну, у нас граф неориентированный, можно туда сюда ходить. И, в общем, у этих соседей расстояние 1.

192: Ну, от стартовой до соседей расстояние 1, то есть такой, как бы следующий уровень. Потом у нас могли быть соседи соседей.

193: Вот, причём могло быть вот такое ребро внутри уровня. Ну, мы его должны были игнорировать, поскольку с этими вершинами уже все понятно. Вот. И соседи соседей, ну и в том числе есть, как бы, по сути, это ребро из этого 1 уровня обратно в 0, ну,

194: Опять же, зачем оно нам надо? Мы уже были в старте. Зачем возвращаться? Так вот, соседи соседей. Причём могли быть циклы, да это же лабиринт, у них расстояние от старта 2. Вот опять же.

195: Могло быть какое-то вот такое ребро, а точнее такого ребра быть не могло. Иначе бы мы эту вершину все-таки на 1 уровне посмотрели, она была бы соседом старта. Вот. То есть на самом деле, если мы посмотрим теперь на соседей 2 уровня, они все

196: Либо находятся на 1 уровне, мы уже их смотрели, либо они находятся на следующем.

197: Как-то так это уже 3 уровень. То есть у нас вот такой как бы алгоритм у нас не может быть ребра с какого-нибудь там уровня, кроме на 2, кроме как на 2 соседних, потому что, ну мы не можем от расстояния 1 перейти к расстоянию 3. А почему

198: Когда не расстояние 2 до старта. Вот, то есть у нас такой как бы волновой алгоритм, можно сказать, мы начинаем вот с какой-то точки на лабиринте и расстояние вот так расходится от неё волнами, ну или тоже самое.

199: На графи в общем виде мы начинаем вот здесь, и у нас расходится такая волна.

200: По расстояниям, по уровням вот такой волновой алгоритм это тоже 1 из вариантов обхода графа. Ну или, во всяком случае, компоненты связанности графа. Вот в чем тут история в том, что мы не

201: Углубляемся если мы углубляемся, мы, наоборот, скорее всего, будем плохие расстояния считать здесь мы наоборот, мы смотрим как бы на всех соседей вершины с сразу не то что ну то есть по очереди, конечно, но не так, как v фсе посмотрели на соседа и переключили.

202: На него не так, мы сначала смотрим, помечаем всех соседей там текущим расстоянием единица, а потом только переходим к соседям соседей. Вот. То есть тут уже все происходит не как бы по стеку или по рекурсии, а скорее именно по очереди. Вот.

203: Такой алгоритм, когда мы от вершины сначала смотрим на всех её соседей и именно на них. То есть причём, посмотри, сначала смотрим на всех соседей, а потом только начинаем смотреть на соседей, соседей. Это называется поиск в ширину.

204: Поиск в ширину.

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

206: Очереди в джаве тоже называется наверное как-нибудь ray кью в питоне тоже какой-то q есть вот ну то есть что такое у нас понятие очереди очень просто. Кто 1 пришёл, тот 1 из очереди и ушёл. Вот.

207: Как выглядит сам алгоритм? Ну мы изначально там в очередь добавляем вершину 0, ну или стартовую вершину. Давайте говорить вершину с и там где-нибудь у нас есть массив расстояний, изначально заполненный

208: Каким-нибудь очень большим числом плюс бесконечность так называемая. Ну и верши стартовой вершине, мы ставим расстояние нулевое сразу же. Вот. Ну и дальше мы, собственно, работаем, пока у нас очередь не опустеет.

209: Пока у нас очередь не пустая, её размер больше нуля. Что мы делаем? Сначала мы достаём 1 элемент из очереди. Вот.

210: Достаём 1 элемент из очереди. Так, наверное, придётся убрать.

211: Ну и сразу же его оттуда удаляем фронт. Это 1 элемент очереди. Ну то есть тот, кто в очереди 1, собственно, стоит поп, это удаление этого 1. Вот. Потом мы просто проходимся по соседям.

212: Текущая вершина.

213: Так же как в дфс. Вот, ну и на самом деле, возможно мы захотим обновить им расстояние. Возможно эти соседи наоборот, были перед нами, конечно, да, но, возможно их пока ещё и не было. Тогда им нужно поставить расстояние, то есть

214: Расстояние до нашего соседа, в котором мы никогда ранее не были, это, конечно же, на единицу больше, чем наше. Можно пользоваться массивом вис. Точно также, в принципе можно этого и не делать. Можно идти там добавлять ребёнка в очередь, ну или, скорее, соседа в очередь.

215: Если мы в нём ещё не были, то есть у нас его with 0, ну или можно вот такой хитрый трюк написать, если мы возьмём наше расстояние нашей вершины кур.

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

217: И, собственно, в этот момент расстояние соседа изменить на вот такое, то есть наше + 1. Почему + 1, потому что + 1 шаг до него проходит + 1 ребро, вот, и в очередь закинуть этого сына. То есть мы

218: Именно что закидываем, мы не переключаем управление на него, мы его просто закидываем, потом следующего соседа закинем ещё следующего и так далее. Если это будет нужно. Вот, ну и все. А потом получается, вот это все закончится, и мы опять с очереди достанем.

219: 1 вершину, опять посмотрим на её соседей и так далее. То есть мы обходим вершины и добавляем их в очередь по совместительству, именно в порядке неубывания расстояний от стартовой до каждой вершины. Вот.

220: Такой алгоритм, как видно, тоже работает за линию n плюс m. Каждая вершина 1 раз оказывается в очередь, 1 раз уходит оттуда и 1 раз смотрит на всех своих соседей вот здесь немного сложный граф, потому что он на плоскости, так сказать.

221: В принципе, можно было хранить вот эти вершины. Ну, вершинами у нас являются клеточки, а переходы, собственно, ну, переходы между рёбрами, переходами, между клеточками. Хранить клетки можно было в виде пар чисел строка и столбец.

222: Можно было закодировать, как бы аля захэшировать пару в 1 число, можно было свою структуру данных написать свой класс там и так далее. Вот графф можно было не строить. То есть ребра можно было не строить. В принципе, для каждой вершины нам можно

223: Вместо этого цикла просто смотреть на 4 соседние клетки, вот на 4 соседние клетки, если у нас соседняя клетка не там, ну, не посещена. И ещё, конечно, у нас тут, в этом лабиринте будет условие, что соседняя клетка, куда мы хотим пойти, она не должна быть там завален.

224: Деревом, то есть она там ноликом помечена, мы в неё идём, вот как обходить 4 соседей в лабиринте, чтобы не писать 4 отдельных ифа типа сначала пойдём на шажок вверх, потом the

225: Влево, вправо, вниз есть такой трюк и он распространяется и на 8 направлений. И вообще, в принципе, это завести вот такие вот массивы. Давайте я их сначала заведу, а потом поясню, что это значит.

226: Ну, это на самом деле есть такие массивы смещений. То есть, если мы вот возьмём от каждого массива нулевую ячейку, у нас получится 0 - 1, то есть 0 по иксу, - 1 по игреку, ну, типа 0 по иксу вправо. Ну то есть вот здесь

227: Остаёмся, а - 1 по игреку идём, получается, вниз вот там следующая клетка ну опять же мне почему-то в лабиринтах удобнее за x номер строки обозначать. Не знаю почему. Так, если вам удобнее понимать.

228: X, как координата, которая влево, вправо идёт. Ну, это здорово, вот тут тут разницы никакой. Следующее, допустим, 1 0 это ход вправо, потому что на 1 по иксу 0, по игреку, ну и так далее. То есть таким образом у нас

229: Икс итое и д игрек итое для какого-то и задаёт очередное смещение, то есть очередной ход, очередной вариант хода, чтобы от клетки икс игрек сходить в итом направлении. Ну там вот 4 направления.

230: Мы берём вот так делаем x plus д икс итое, игрек плюс д игрек итое. Нужно только проверить, что вот эта новая клетка не выходит за границы нашего поля, что она не является заваленной деревом, ну и потом.

231: Уже проверять там по расстояниям или по визите в бфсе. Вот такой вот алгоритм, как видно, если его запускать на, то есть на ориентированных графах все тоже самое работает для него, если его запускать на неё.

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

233: Ну, в принципе, наверное, это все детали, задачи. A4. Есть ли по ней вопросы?

234: Карту на 2 клетки больше сделать, чтобы, да, удобно. Очень хорошее предложение вокруг всего поля. То есть занумеровать наше поле с единицы, а как бы нулевую рамочку и вот эти вот рамочки забить деревьями тогда.

235: Не придётся проверять, что мы выходим где-то за границы поля. Можно будет просто проверять, чтоб мы не наступили на закрашенную клетку. Вот.

236: В принципе хорошая конструкция вот может быть ещё вопросы предложения x. Больше 1 нет да, конечно x больше равно 1 в условии это да, но это скорее потому что обычно в задачах все с единицы нумеруют в входных данных вот.

237: То есть это уже в принципе, ну да, это намекает, но это все равно наш выбор занумеровать, и нам само поле с единицы, с нуля. Вот.

238: Ну, тут, оказывается, нумерация соединится удобнее, да, чтобы нолики, а ещё там энную строку, и мы столбец n plus, 1 строку м плюс 1 столбец закрасить.