CF2045L.Buggy DFS

NOI/NOI+/CTSC

通过率：0%

AC君温馨提醒

该题目为【codeforces】题库的题目，您提交的代码将被提交至codeforces进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

你正在学习一种名为深度优先搜索（DFS）的图遍历算法。然而，由于一个小错误，你的算法与标准版本略有区别。以下是你实现的有误深度优先搜索（BDFS）算法，假设图中有 $N$ 个节点（编号从 $1$ 到 $N$ ）。

BDFS():
  令 S 为一个空栈
  令 FLAG 为大小为 N 的布尔数组，初始值均为 false
  令 counter 为一个整数，初始化为 0

  将 1 压入栈 S

  当 S 不为空时：
    弹出 S 的栈顶元素到 u
    FLAG[u] = true

    对于 u 的每个邻居 v（按升序访问）：
      counter = counter + 1
      如果 FLAG[v] 为 false：
        将 v 压入栈 S

  返回 counter

你发现这个错误让算法比标准的 DFS 慢。通过查看函数 BDFS() 的返回值可以探究这个问题。为了更好地研究算法的行为，你打算构造一些无向简单图，让函数 BDFS() 的返回值等于 $K$ ，或者确定这样的图是否存在。