게임 그래프
골드 II의견: 0
알리와 베리가 방향 비순환 그래프(DAG) 위에서 토큰 게임을 한다. 그래프에는 \(N\)개의 노드와 \(M\)개의 방향 간선이 있다.
처음에 토큰이 특정 시작 노드에 놓여 있다. 두 플레이어는 번갈아 가며(알리 먼저) 토큰을 현재 노드에서 나가는 간선을 따라 인접한 노드로 이동시킨다. 이동할 수 있는 간선이 없는 경우(나가는 간선이 전혀 없는 노드에 토큰이 있는 경우) 그 플레이어가 진다.
두 플레이어 모두 최선의 전략을 쓴다고 할 때, \(Q\)개의 시작 노드 각각에 대해 누가 이기는지 출력하여라.
- \(1 \le N \le 100\,000\)
- \(0 \le M \le 200\,000\)
- \(1 \le Q \le 100\,000\)
- 그래프에 사이클이 없다(DAG).
- 자기 자신으로 가는 간선은 없다.
첫째 줄에 노드 수 \(N\), 간선 수 \(M\), 질의 수 \(Q\)가 공백으로 구분되어 주어진다.
다음 \(M\)개의 줄에 방향 간선 \((u, v)\)가 한 줄에 하나씩 주어진다.
다음 \(Q\)개의 줄에 시작 노드 번호가 한 줄에 하나씩 주어진다.
\(Q\)개의 줄에 걸쳐 각 질의에 대해 First 또는 Second를 출력한다.
3 3 3
1 2
1 3
2 3
1
2
3
First
First
Second
노드 \(3\)은 나갈 간선이 없어 Grundy 값이 \(0\) → 지는 위치. 노드 \(2\)는 \(\{0\}\)의 mex = \(1\) → 이기는 위치. 노드 \(1\)은 \(\{1, 0\}\)의 mex = \(2\) → 이기는 위치.
4 3 4
1 2
1 3
1 4
1
2
3
4
First
Second
Second
Second
노드 \(2, 3, 4\)는 모두 싱크(Grundy=\(0\), 지는 위치). 노드 \(1\)에서 \(\{0,0,0\}\)의 mex = \(1\) → 이기는 위치.
riseoj 작성
출처 Original
평가 및 의견
게임 그래프
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
게임 그래프