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

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

Эта тема будет местом обсуждения курса “Алгоритмы на графах” для 3 курса ФИИТ. Задавайте вопросы по курсу, задачам и пр.

Страница с материалами курса.

#2

Сразу орг момент. Практику переносим, как я и планировал, на следующую неделю. Итак, 17.09.2015 в 15:20 аудитория 315. Можно приходить со своими ноутбуками.

1 лайк
#3

Роман Борисович, при попытке отправить решение, на 3 разных компиляторах вылетает ошибка компиляции! Программа компилируется на студии и работает! Что делать?

#4

000009.c:1:20: fatal error: iostream: No such file or directory #include

#5

Убрал iostream, теперь на вектор ругается!

#6

Можете меня принять, не могу посмотреть задачу?!

#7

От отчаяния, наподключал все что можно, получил ошибку Check failed, и в таблице View report пишет N/A, и теперь я вообще не понимаю, что фатального в моем решении, что он не может проверить?

#8

@Anatolij_Abramov gcc - это компилятор языка С, а не С++. И я не знаю, почему clang++ должен знать константу INT_MAX. Неужели lc (MS VS) ее знает?

@Frag добавил

#9

Можете меня принять на ejudge?

#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

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