Разбор задачи «Две смены на станции»

1. Идея

Нужно проверить, можно ли каждому посту назначить одну из двух смен так, чтобы у любых соседних постов смены были разными.

Если перевести это на язык графов:

• посты — это вершины графа;
• пары соседних постов — это рёбра;
• нужно раскрасить вершины в 2 цвета так, чтобы концы любого ребра имели разные цвета.

Это классическая проверка на двудольность графа.

Если граф можно раскрасить в два цвета без конфликтов, ответ YES, иначе NO.

2. Наблюдения

Наблюдение 1

Если вершина уже покрашена в цвет 0, то все её соседи обязаны иметь цвет 1.

И наоборот: если вершина цвета 1, то все её соседи должны быть цвета 0.

Наблюдение 2

Если в процессе окажется, что две соседние вершины должны иметь один и тот же цвет, то требуемое расписание невозможно.

Тогда сразу выводим NO.

Наблюдение 3

Граф может быть несвязным, то есть состоять из нескольких компонент связности.

Поэтому нельзя запускать обход только из вершины 1. Нужно пройти по всем вершинам и, если какая-то ещё не покрашена, начать обход из неё.

Наблюдение 4

Повторяющиеся рёбра не мешают решению. Они просто несколько раз проверят одно и то же условие.

3. Алгоритм

Будем обходить граф в ширину, используя BFS.

1. Считываем n и m.
2. Строим список смежности.
3. Создаём массив color длины n + 1.
   • -1 означает, что вершина ещё не покрашена;
   • 0 и 1 — две смены.
4. Для каждой вершины от 1 до n:
   • если она уже покрашена, пропускаем;
   • иначе красим её в 0 и запускаем BFS.
5. В BFS:
   • достаём вершину v;
   • для каждого соседа to:
     • если to ещё не покрашен, красим его в противоположный цвет: 1 - color[v];
     • если to уже покрашен и его цвет совпадает с color[v], выводим NO и завершаем программу.
6. Если все компоненты удалось обработать без конфликтов, выводим YES.

4. Почему это работает

Докажем, что алгоритм корректен.

Почему раскраска через BFS верна

Когда мы впервые попадаем в вершину, мы назначаем ей цвет. После этого всем её соседям пытаемся назначить противоположный цвет.

Это точно соответствует условию задачи: соседние посты не должны работать в одну смену.

Почему конфликт означает невозможность ответа YES

Если мы нашли ребро v - to, у которого color[v] == color[to], значит две соседние вершины имеют одинаковую смену.

Это прямо нарушает условие задачи. Значит корректного расписания не существует, и ответ должен быть NO.

Почему отсутствие конфликтов означает, что ответ YES

Если обход всех компонент завершился и ни разу не возникло ребра с одинаковыми цветами на концах, значит мы действительно построили корректное разбиение всех вершин на две группы.

То есть одну группу можно поставить в первую смену, а вторую — во вторую. Следовательно, ответ YES.

Почему нужно обходить все вершины

Граф может быть несвязным. Если проверить только одну компоненту, можно не заметить конфликт в другой. Поэтому внешний цикл по всем вершинам обязателен.

5. Сложность

Пусть n — число вершин, m — число рёбер.

• Построение графа: O(m)
• Обход BFS по всем компонентам: O(n + m)

Итоговая сложность: O(n + m)

Память:

• список смежности: O(n + m)
• массив цветов: O(n)
• очередь BFS: O(n)

Итоговая память: O(n + m)

6. Код на C++17

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

int main() {
    int n, m;
    cin >> n >> m;

    vector<vector<int>> g(n + 1);
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }

    vector<int> color(n + 1, -1);
    queue<int> q;

    for (int start = 1; start <= n; start++) {
        if (color[start] != -1) {
            continue;
        }

        color[start] = 0;
        q.push(start);

        while (!q.empty()) {
            int v = q.front();
            q.pop();

            for (int to : g[v]) {
                if (color[to] == -1) {
                    color[to] = 1 - color[v];
                    q.push(to);
                } else if (color[to] == color[v]) {
                    cout << "NO\n";
                    return 0;
                }
            }
        }
    }

    cout << "YES\n";
    return 0;
}

7. Код на Python 3

from collections import deque

n, m = map(int, input().split())

g = [[] for _ in range(n + 1)]
for _ in range(m):
    u, v = map(int, input().split())
    g[u].append(v)
    g[v].append(u)

color = [-1] * (n + 1)

for start in range(1, n + 1):
    if color[start] != -1:
        continue

    color[start] = 0
    q = deque([start])

    while q:
        v = q.popleft()
        for to in g[v]:
            if color[to] == -1:
                color[to] = 1 - color[v]
                q.append(to)
            elif color[to] == color[v]:
                print("NO")
                raise SystemExit

print("YES")