Алгоритм называется "обход в глубину на графе". Работает за линию, все очень быстро. Правда, его придется применить несколько раз.
Все неравенства "==" замените на пару "<=" и ">=".
Добавьте неравенства 1 < 2, 3 < 4 и т.д. для каждой пары соседних на числовой прямой чисел во входных данных
Постройте граф: Каждой переменной и уникальному числу во входных данных сопоставьте одну вершину. Проведите для каждого неравнества ребро от меньшей вершины к большей, раскрашенное в 2 цвета: черный, если неравнество нестрогое (
<=), белый - иначе.
Теперь, если в этом графе нет циклов, содержащих белые ребра (строгие неравенства) - то противоречий нет: Все циклы целиком из черных ребер означают, что все вершины имеют одинаковое значение. Можно эти вершины все объединить в одну новую. Раз белые ребра (
<) циклов не образуют, то получившийся граф будет ациклическим и можно назначить всем вершинам какие-то числовые значения, удовлетворяющие условиям. Проблема может еще быть, что нет целых решений вроде 1== a < b < c == 2, но это можно потом проверить в топологической сортировке жадно назначая всем вершинам числа. Или противоречия вида 2==3. Тоже решается после получения компонент связности.
Итак, алгоритм: найдите в этом графе
компоненты сильной связности. Потом проверьте все ребра. Если белое ребро (строгое неравнество) имеет оба конца в одной и той же компоненте - вы нашли противоречие.
Теперь надо постараться назначить кадой компоненте числовое значение так, чтобы не было противоречий. Это можно делать жадно, назначая каждой компоненте минимально возможное значение.
Пройдитесь по компонентам в топологическом порядке (они в таком виде уже будут получены алгоритмом выше). Если в компоненте есть вершина-число, то назначаете всей компоненте это значение. Если есть несколько вершин-чисел - то это противоречие. Также посмотрите все обратные ребра из всех вершин в компоненте. Если они ведут в другую компоненту, то обновите минимально возможное значение в данной компоненте как равное, или на 1 большее уже известного значения для второй компоненты (в зависимости от цвета ребра, т.е. строгости неравнества). Если получили, что это минимально возможное значение больше уже фиксированного за счет вершины-числа - то вы нашли противоречие.
В конце вы получите для каждой компоненты ее численное значение без каких-либо противоречий.
