Философские вопросы

1. В разделе полезные ссылки появилась Алгоритмика
2. Решение задачек в теории затачивает ваш мозг. Реализация делает это еще эффективнее. Не пренебрегайте этим родом деятельности)
3. Вспомним, что было на прошлых лекциях.
4. Те, кто часто пишет раунды - напишите мне, я вас добавлю в наш локал чат.
5. Всем ли все понятно? Есть ли вопросы/предложения?

Гештальт

Задача на подпоследовательность в строке из предыдущего урока. Как избавиться от константы 27?

Задача - Вывести сколько вершин на каждом уровне дерева

vector<int> depth(n), depth_count(n);
vector<vector<int> > g(n, vector<ll> (0));

void dfs(int v, int d){
	depth[v] = d;
	depth_count[d]++;

	for(int i = 0; i<g[v].size(); i++){
		int to = g[v][i];
		if(!depth[to]) dfs(to, d+1);
	}
}

dfs(0, 1);

Задача - Как определить есть ли цикл в графе?

Эйлеров тур

Делаем dfs

Добавляем в массив вершину дважды - если входим в нее и если выходим