Эта тема будет местом обсуждения курса “Алгоритмы на графах” для 3 курса ФИИТ. Задавайте вопросы по курсу, задачам и пр.
Страница с материалами курса.
Эта тема будет местом обсуждения курса “Алгоритмы на графах” для 3 курса ФИИТ. Задавайте вопросы по курсу, задачам и пр.
Страница с материалами курса.
Сразу орг момент. Практику переносим, как я и планировал, на следующую неделю. Итак, 17.09.2015 в 15:20 аудитория 315. Можно приходить со своими ноутбуками.
Роман Борисович, при попытке отправить решение, на 3 разных компиляторах вылетает ошибка компиляции! Программа компилируется на студии и работает! Что делать?
000009.c:1:20: fatal error: iostream: No such file or directory #include
Убрал iostream, теперь на вектор ругается!
Можете меня принять, не могу посмотреть задачу?!
От отчаяния, наподключал все что можно, получил ошибку Check failed, и в таблице View report пишет N/A, и теперь я вообще не понимаю, что фатального в моем решении, что он не может проверить?
@Anatolij_Abramov gcc - это компилятор языка С, а не С++. И я не знаю, почему clang++ должен знать константу INT_MAX. Неужели lc (MS VS) ее знает?
@Frag добавил
Можете меня принять на ejudge?
Посмотрел крёстного отца, не выдержал
Та-дам тсс
@Svetly а я не вижу, чтобы Светличный Александр записался ко мне на курс. Я про бумажный документ.
@Goga флудить в ВК, пожалуйста
Я одним из первых к вам записался
На втором занятии
Как обходиться с такой вот штукой?
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).
Кстати, последнее в любом случае стоит сделать. Не знаю почему сразу не сказал об этом.
Кажется, я говорил на прошлой лекции и повторю снова: удалять неблагодарное дело, лучше помечать.