The graph does not contain multiple edges, and also does not contain self-loops. Besides, the graph is connected, which means each vertex can reach any other vertices through edges.Cuber QQ will flag some vertices in the graph, which aims to make every vertex in the graph has exactly one flagged neighbor vertex.Cuber QQ wants to know the least number of vertices that have to flag.
Cuber QQ receives a task that contains a graph with n n vertices and n n edges. The graph does not contain multiple edges, and also does not contain self-loops. Besides, the graph is connected, which means each vertex can reach any other vertices through edges. Cuber QQ will flag some vertices in the graph, which aims to make every vertex in the graph has exactly one flagged neighbor vertex. Cuber QQ wants to know the least number of vertices that have to flag.
(图片来源网络,侵删)