Orange Boy Can You Solve It Out? Ep. 50

anniversary 思考题

Very Easy Problem

Wow! OBCYSIO has reached 50 episodes! Let's celebrate using a very popular and easy problem.

Hikari and Ninetail are playing a game on an undirected graph of N nodes and M edges. They move in turns, with Hikari being the first one. For each turn, the player must find a cycle in the graph and remove one edge on it (she gets to choose which one she removes). The game continues until the graph has no cycle. The player who cuts the last edge wins.

It is not guaranteed that the graph is connected. It is also possible for it to have self-loops or multiple edges between the same pair of nodes.

A cycle is a sequence of distinct node C_i that (C_i,C_{i+1})\in E with \forall 1\leq i\leq |C|-1 and (C_{|C|},C_{1})\in E

Given the graph, your task is to find out who will win if both players are playing optimally.

版权声明:
作者:XGN
链接:https://blog.hellholestudios.top/archives/804
来源:Hell Hole Studios Blog
文章版权归作者所有,未经允许请勿转载。

THE END
分享
二维码
< <上一篇
下一篇>>
文章目录
关闭
目 录