Алгоритмы на графах (осень 2015)

Поддержка учебных курсов ФИИТ, 3 курс
#10

Посмотрел крёстного отца, не выдержал

2 лайка
#11

Та-дам тсс

#12

@Svetly а я не вижу, чтобы Светличный Александр записался ко мне на курс. Я про бумажный документ.

@Goga флудить в ВК, пожалуйста

#13

Я одним из первых к вам записался

#14

На втором занятии

#15

Как обходиться с такой вот штукой?

000071.cpp: In function ‘int main()’:

000071.cpp:14:34: error: use of deleted function ‘std::basic_fstream::basic_fstream(const std::basic_fstream&)’

 auto in = fstream("input.txt");
О конструкторах копии
О конструкторах копии
#16 
freopen("input.txt", "r", stdin);

и вот тебе счастье

UPD: вообще не ejudge можно же использовать stdout\stdin

#17

Роман Борисович, что-то на лекции вы нас обманули. Я сразу смутился, но немного засомневался.

Тот алгоритм поиска Эйлерова цикла не линейный. Нужно удалять ребра за константу, удалять “явно”, то есть больше к ним не обращаться.

Вот даже вам супертест, на котором алгоритм работает нелинейное время: 2 вершины и 1000 ребер между ними. if (used[to.id] == false) выполнится же O(M^2) раз.

Это с лекции:

dfs(v)
   for to: g[v]
      if (used[to.id] == false)
          used[to.id] = true
          dfs(to.next)
   answer.push(v)

А вот так было бы ок

dfs(v)
   while ptr[v] < SIZE(g[v])
       to = g[v][ptr[v]]
       if (used[to.id] == false)
            used[to.id] = true
            dfs(to.next)
       ++ptr[v]
   answer.push(v)
#18

Роман Борисович, а разрешено ли пользоваться структурами, взятыми из интернета(например, список смежностей)?

#19

@Goga вот Вы со своими мув-конструкторами :slight_smile: А вдруг у объекта его нет? Напишите классически или как Степан предложил.

@pletnev_alexander а) Я разрешил использовать Интернет в любых объемах. б) Я не рассказал как реализовать список смежностей???

@kvark161 А может это Вы нас тут обманываете? Во-первых, кто разрешал Вам кратные ребра использовать? С точки зрения Эйлерова графа - это совершенно бессмысленно и на этапе чтения можно сразу отсечь пары кратных ребер. Во-вторых, посмотрите e-max или Кормена, они Ваш эксклюзив тоже не рассматривают. В третьих, заведите для каждой вершины указатель на первое не помеченное ребро и будет Вам O(M).

Кстати, последнее в любом случае стоит сделать. Не знаю почему сразу не сказал об этом.

О конструкторах копии
#20

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

#21

Да, по Kvark’у сработало.

#22

О! Что-то я Ваш код не дочитал. Так Вы сами же предлагаете не удалять, а помечать.

@Goga вы лучше скажите что не работает :slight_smile:

#23

На имаксе вообще что-то странное, там матрица смежности, квадрата по вершинам так не избежать. И, кстати, там решают задачу на мультиграфе с петлями.

#24

А в Кормене вообще поиск Эйлерова цикла дано как упражнение: разработайте алгоритм тралала…

*издание 2е

#25

Да, на e-maxx действительно что-то странное. Про Кормена верю на слово. Тогда вопрос: откуда я все это взял? :smiley: В любом случае, никаких кратных ребер я не обещал. Да, и усовершенствование с хранением первого осмысленного ребра просто второпях забыл.

#26

Тогда вопрос такой: как доказать асимптотику без кратных ребер? В одну вершину мы все равно можем прийти очень много раз и будет проверять все исходящие из нее ребра.Например, граф ‘цветочек’, одна вершина через которую проходит куча циклов длины 3. Мы будем заходить в центральную столько раз, сколько циклов длины 3, а их О(n).

#27

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

#28

@RS Роман Борисович, здравствуйте! Сегодня, 6 октября 2015 года, Вы будете на мехмате или нет?

#29

Да, я на мехмате с 16:00. Завтра буду 14:00-18:00