Порядок сборки механизма

1. Идея

Зависимости между деталями удобно рассматривать как ориентированный граф:

• вершины — детали;
• ребро a -> b означает, что a нужно установить раньше b.

Тогда задача сводится к проверке: есть ли в этом ориентированном графе цикл.

Почему именно так:

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

Для проверки используем алгоритм Кана — топологическую сортировку через входящие степени.

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

Наблюдение 1

Если у некоторой детали входящая степень равна 0, значит ни одна другая деталь не обязана стоять перед ней. Такую деталь можно ставить первой среди оставшихся.

Наблюдение 2

Если мы "удалили" деталь из рассмотрения, то все её исходящие зависимости тоже перестают мешать. То есть для всех деталей, в которые из неё шли ребра, входящая степень уменьшается на 1.

Наблюдение 3

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

Наблюдение 4

Если удалось обработать все n деталей, то порядок сборки существует, значит ответ YES.

3. Алгоритм

1. Считываем n и m.
2. Строим список смежности g, где g[a] содержит все вершины b, такие что есть зависимость a -> b.
3. Считаем массив входящих степеней indegree, где indegree[v] — сколько зависимостей требуют поставить что-то раньше вершины v.
4. Помещаем в очередь все вершины с indegree[v] == 0.
5. Пока очередь не пуста:
   • извлекаем вершину v;
   • увеличиваем счетчик обработанных вершин;
   • для каждой вершины to из g[v] уменьшаем indegree[to];
   • если indegree[to] стал равен 0, добавляем to в очередь.
6. После завершения:
   • если обработано n вершин, выводим YES;
   • иначе выводим NO.

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

Докажем корректность.

Почему вершину с нулевой входящей степенью можно брать сейчас

Если indegree[v] == 0, то нет ни одной зависимости вида x -> v среди ещё не удалённых вершин. Значит, установка v сейчас не нарушает ни одного требования.

Что делает удаление вершины

Когда мы обрабатываем вершину v, считаем, что поставили эту деталь в порядок сборки. После этого ограничения вида v -> to уже выполнены, поэтому их можно убрать. Именно поэтому мы уменьшаем indegree[to].

Почему если обработали все вершины, ответ YES

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

Почему если обработали не все вершины, ответ NO

Предположим, очередь опустела раньше времени. Это значит, что среди оставшихся вершин нет ни одной с входящей степенью 0. То есть у каждой оставшейся вершины есть хотя бы одна зависимость от другой оставшейся вершины. В конечном ориентированном графе такая ситуация возможна только при наличии цикла. А цикл делает корректный порядок невозможным.

Следовательно, алгоритм верно определяет, можно ли собрать механизм.

5. Сложность

• Построение графа: O(m)
• Работа алгоритма Кана: O(n + m)

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

Память:

• список смежности: O(n + m)
• массив входящих степеней и очередь: 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);
    vector<int> indegree(n + 1, 0);

    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        g[a].push_back(b);
        indegree[b]++;
    }

    queue<int> q;
    for (int v = 1; v <= n; v++) {
        if (indegree[v] == 0) {
            q.push(v);
        }
    }

    int processed = 0;

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

        for (int to : g[v]) {
            indegree[to]--;
            if (indegree[to] == 0) {
                q.push(to);
            }
        }
    }

    if (processed == n) {
        cout << "YES\n";
    } else {
        cout << "NO\n";
    }

    return 0;
}

7. Код на Python 3

from collections import deque

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

g = [[] for _ in range(n + 1)]
indegree = [0] * (n + 1)

for _ in range(m):
    a, b = map(int, input().split())
    g[a].append(b)
    indegree[b] += 1

q = deque()
for v in range(1, n + 1):
    if indegree[v] == 0:
        q.append(v)

processed = 0

while q:
    v = q.popleft()
    processed += 1

    for to in g[v]:
        indegree[to] -= 1
        if indegree[to] == 0:
            q.append(to)

if processed == n:
    print("YES")
else:
    print("NO")