一个图有n个顶点，并且有大于n-1条边，这个图一定有环。那么，这个图是包括“无向图”和“有向图”吗？

如图所示。一个图有n个顶点，并且有大于n-1条边，这个图一定有环。那么，这个图是包括“无向图”和“有向图”吗？

很明显，是无向图，如果有向图，很容易找到反例。

• 这个问题的回答你可以参考下: https://ask.csdn.net/questions/7683399
• 这篇博客你也可以参考下：《手撕力扣链表题》反转链表、删除链表的倒数第 N 个结点
• 除此之外, 这篇博客: 有N个台阶，一步可以走一梯或者两梯，请问有多少种走法中的 动态规划 部分也许能够解决你的问题, 你可以仔细阅读以下内容或跳转源博客中阅读:
  

• 可以使用动态规划

  dp[n]就代表第n梯的走法

  function calcWalkWay(n) {
  	if (n <= 2) return n
      
      const dp = []
      dp[1] = 1
      dp[2] = 2
      
      for (let i = 3; i <= n; i++) {
          dp[i] = dp[i-1] + dp[i-2]
      }
      return dp[n]
  }
  

  根据上面的还可以对数据优化

  function calcWalkWay(n) {
  	if (n <= 2) return n
     
      let pre = 1
      let current = 2
      
      for (let i = 3; i <= n; i++) {
          //[current, pre] = [current + pre, current]
          const temp = current
          current = current + pre
          pre = temp
      }
      return current
  }
  

• 以下回答由chatgpt基于相关博客总结生成:

  根据题目描述，图有n个顶点，且有大于n-1条边，说明这个图肯定是连通图，不存在孤立的顶点。一个无向图只有在每个顶点的度数都是偶数时，才能有欧拉回路。而有向图只有在每个顶点的出度等于入度时，才能有欧拉回路。根据题目描述，图中一定有环，所以不存在无向图的情况，只能是有向图。

  因此，可以判断图是属于“有向图”。