На втором занятии
Как обходиться с такой вот штукой?
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");
freopen("input.txt", "r", stdin);
и вот тебе счастье
UPD: вообще не ejudge можно же использовать stdout\stdin
Роман Борисович, что-то на лекции вы нас обманули. Я сразу смутился, но немного засомневался.
Тот алгоритм поиска Эйлерова цикла не линейный. Нужно удалять ребра за константу, удалять “явно”, то есть больше к ним не обращаться.
Вот даже вам супертест, на котором алгоритм работает нелинейное время: 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)Роман Борисович, а разрешено ли пользоваться структурами, взятыми из интернета(например, список смежностей)?
@Goga вот Вы со своими мув-конструкторами 
А вдруг у объекта его нет? Напишите классически или как Степан предложил.
@pletnev_alexander а) Я разрешил использовать Интернет в любых объемах. б) Я не рассказал как реализовать список смежностей???
@kvark161 А может это Вы нас тут обманываете? Во-первых, кто разрешал Вам кратные ребра использовать? С точки зрения Эйлерова графа - это совершенно бессмысленно и на этапе чтения можно сразу отсечь пары кратных ребер. Во-вторых, посмотрите e-max или Кормена, они Ваш эксклюзив тоже не рассматривают. В третьих, заведите для каждой вершины указатель на первое не помеченное ребро и будет Вам O(M).
Кстати, последнее в любом случае стоит сделать. Не знаю почему сразу не сказал об этом.
Кажется, я говорил на прошлой лекции и повторю снова: удалять неблагодарное дело, лучше помечать.
Да, по Kvark’у сработало.
О! Что-то я Ваш код не дочитал. Так Вы сами же предлагаете не удалять, а помечать.
@Goga вы лучше скажите что не работает
На имаксе вообще что-то странное, там матрица смежности, квадрата по вершинам так не избежать. И, кстати, там решают задачу на мультиграфе с петлями.
А в Кормене вообще поиск Эйлерова цикла дано как упражнение: разработайте алгоритм тралала…
*издание 2е
Да, на e-maxx действительно что-то странное. Про Кормена верю на слово. Тогда вопрос: откуда я все это взял? 
В любом случае, никаких кратных ребер я не обещал. Да, и усовершенствование с хранением первого осмысленного ребра просто второпях забыл.
Тогда вопрос такой: как доказать асимптотику без кратных ребер? В одну вершину мы все равно можем прийти очень много раз и будет проверять все исходящие из нее ребра.Например, граф ‘цветочек’, одна вершина через которую проходит куча циклов длины 3. Мы будем заходить в центральную столько раз, сколько циклов длины 3, а их О(n).
Именно этот пример пришел мне в голову сегодня утром и да, я согласен, что то что я считал усовершенствованием, жизненно необходимо. Только ребра все равно не удаляйте.
Да, я на мехмате с 16:00. Завтра буду 14:00-18:00
Роман Борисович, скажите пожалуйста, завтра Вы будете на кафедре? И когда лучше подойти, если да?
Институт математики, механики и компьютерных наук ЮФУ, 2005–2021