Игра на графе: различия между версиями

Материал из Algocode wiki
Перейти к: навигация, поиск
Строка 32: Строка 32:
  
 
void dfs(int v) {
 
void dfs(int v) {
used[v] = 1;
+
    used[v] = 1;
for (auto to : g[u]) {
+
    for (auto to : g[u]) {
if (!used[to]) {
+
        if (!used[to]) {
                        --degree[to];  
+
            --degree[to];  
if (L[v]) {
+
        }
                                W[to] = 1;
+
        if (L[v]) {
                        }
+
            W[to] = 1;
else if (degree[to] == 0) {
+
        }
L[to] = 1;
+
        else if (degree[to] == 0) {
                        }
+
            L[to] = 1;
else {
+
        }
continue;
+
        else {
                        }
+
            continue;
dfs(to);
+
        }
}
+
        dfs(to);
        }
+
    }
 
}
 
}
 
</syntaxhighlight>
 
</syntaxhighlight>

Версия 13:13, 9 февраля 2020

Задача

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

Идеи

Мы знаем, что если из вершины есть переход в проигрышную вершину - она выигрышная.

Если из вершины все ребра идут только в выигрышные вершины - она проигрышная.

Решение

На каждом шаге алгоритма для каждой вершины будем пытаться посчитать ответ, проверив все соседние с ней вершины, если ответ не обновился ни для одной вершины, то нам уже известны все ответы(если вершина помечена проигрышной/выигрышной - то она такой и является, иначе она - ничейная, так как если мы не можем обновить ответ ни для одной вершины, то у нас остались только такие вершины, на которых мы можем играть бесконечно).

Такое решение уже работает за $O(mn)$, существуют и проще решения за такую асимптотику. Давайте придумаем, как улучшить наше решение.

У нас есть вершины, про которые изначально известно, что они проигрышные(это листья). Из каждой из таких вершин пустим поиск в глубину по обратным рёбрам. Для каждой вершины может быть три варианта :

1) Она уже помечена проигрышной или выигрышной, но тогда мы можем просто не запускаться в нее, так как из нее DFS уже был запущен.

2) Если вершина, в которую мы хотим запуститься, еще не была помечена и при этом мы сейчас запускаемся из проигрышной вершины, просто пометим вершину выигрышной.

3) Если вершина, в которую мы хотим запуститься, еще не была помечена и при этом мы сейчас запускаемся из выигрышной вершины, посмотрим все ли уже ребра были просмотрены для той вершины, в которую мы хотим запуститься.(Проверку на то что все ребра из вершины уже были просмотрены можно осуществлять с помощью вспомогательного массива $degree_{u}$, в котором мы будем хранить количество непросмотренных ребер из вершины $u$).

Тогда в конце алгоритма будут три типа вершин : проигрышные/выигрышные/вершины со степенью $degree_{u} > 0$, но как мы уже сказали, если для вершины нельзя сказать, какая она после $n$ шагов - она ничейная.

Код

 1 vector<int> g[N];
 2 bool W[N], L[N], used[N];
 3 int degree[N];
 4 
 5 void dfs(int v) {
 6     used[v] = 1;
 7     for (auto to : g[u]) {
 8         if (!used[to]) {
 9             --degree[to]; 
10         }
11         if (L[v]) {
12             W[to] = 1;
13         }
14         else if (degree[to] == 0) {	
15             L[to] = 1;
16         }
17         else {
18             continue;
19         }
20         dfs(to);
21     }
22 }

Сведение игр к игре на графе

Любую равноправную игру, где все возможные ходы из всех вершин нам известны и ход зависит только от игрока, можно свести к игре на графе, так как мы можем сделать все состояния игры вершинами и провести ребра из всех состояний в те состояния, в которые мы можем из них попасть.



Автор конспекта: Глеб Лобанов

По всем вопросам пишите в telegram @glebodin