Семинар 24.02 Подгруппа 106-2

Домашнее задание: Задач на допуск к контесту на этой неделе нет. Есть просто задачка. Дан неориентированный граф. На ребрах графа записаны целые веса w_i. Нужно для данного графа расставить на вершинах целые веса, так что сумма весов на двух вершинах, соединенных ребром, будет равна весу ребра по модулю N, где N - некоторое целое число, которое тоже дается на вход функции.

Если такое невозможно, функция должна об этом сообщить, например, вернуть false.

Вершину в задаче можно представить, например, так:

 struct Edge {
   int weight;
   int to // node index
 };
 struct Node {
   vector<Edge> edges;
 };

Тогда функция будет иметь такой вид:

 bool TryFindNodeWeights(const vector<Node>& graph, vector<int>* result) {
   // result[i] == weight of i-th node.
   // return true if success else false. 
 }

Также нужно написать набор ручных тестов: графы, на котором получилось проставить веса: граф без циклов, граф с четным циклом, граф с нечетным циклом, а также граф на котором не получилось проставить веса.