A1122 Hamiltonian Cycle (25 分| 图论，附详细注释，逻辑分析)

写在前面

• 思路分析
  • 给出1个图，判断给定的路径是不是哈密尔顿路径
    • 1.设置falg1 判断节点是否多⾛、少走、或走成环
    • 2.设置flag2 判断路能不能走通
    • 3.当falg1、 flag2都为1时是哈密尔顿路径，否则不是
• 题目简单，25分钟a题
  • 核心问题，条件转化
    • 要n+1个顶点，每个点都要经过并且回到自己
    • 相邻元素必须有边

测试用例

• input:
  6 10
  6 2
  3 4
  1 5
  2 5
  3 1
  4 1
  1 6
  6 3
  1 2
  4 5
  6
  7 5 1 4 3 6 2 5
  6 5 1 4 3 6 2
  9 6 2 1 6 3 4 5 2 6
  4 1 2 5 1
  7 6 1 3 4 5 2 6
  7 6 1 2 5 4 3 1
  
  output:
  YES
  NO
  NO
  NO
  YES
  NO
  

ac代码

• #include <iostream>
  #include <set>
  #include <vector>
  using namespace std;
  int main()
  {
      int n, m, cnt, k, a[210][210] = {0};
      cin >> n >> m;
      for(int i = 0; i < m; i++)
      {
          int t1, t2;
          scanf("%d%d", &t1, &t2);
          a[t1][t2] = a[t2][t1] = 1;
      }
  
      cin >> cnt;
      while(cnt--)
      {
          cin >> k;
          vector<int> v(k);
          set<int> s;
  
          int flag1 = 1, flag2 = 1;
          for(int i = 0; i < k; i++)
          {
              scanf("%d", &v[i]);
              s.insert(v[i]);
          }
          // 
          if(s.size() != n || k - 1 != n || v[0] != v[k-1]) flag1 = 0;
          for(int i = 0; i < k - 1; i++)
              if(a[v[i]][v[i+1]] == 0) flag2 = 0;
  
          printf("%s",flag1 && flag2 ? "YES\n" : "NO\n");
      }
      return 0;
  }
  

知识点小结

• 欧拉
  • 欧拉通路: 通过图中每条边且只通过一次，并且经过每一顶点的通路
  • 欧拉回路: 通过图中每条边且只通过一次，并且经过每一顶点的回路
  • 无向图是否具有欧拉通路或回路的判定
    • 欧拉通路:图连通；图中只有0个或2个度为奇数的节点
    • 欧拉回路:图连通；图中所有节点度均为偶数
  • 有向图是否具有欧拉通路或回路的判定:
    • 欧拉通路:图连通；除2个端点外 其余节点入度=出度；
    • 1个端点入度比出度大1； 一个端点入度比出度小1 或 所有节点入度等于出度；
    • 欧拉回路:图连通；所有节点入度等于出度
• 哈密顿
  • 哈密顿图是一个无向图
  • 哈密顿通路: 通过图中每个点且只通过一次，并且经过每一顶点的通路。
    • 任意两个顶点的度数之和都不小于n-1（即大于等于n-1）, 则存在哈密尔顿通路
  • 哈密顿回路: 通过图中每个点且只通过一次，并且经过每一顶点的回路。
    • 任意两个顶点的度数之和都不小于n（即大于等于n）, 则存在哈密尔顿回路