给一个n个节点n条边的无向图G，试判断图中是否存在哈密顿路径。
若G中存在哈密顿路径l，则路径端点度数不小于1，其余点度数不小于2。
则G存在哈密顿路径的必要条件：
1）G连通；
2）G中度数为1的点不超过两个。
考虑到简单连通图中边的数目m不超过n，
1）若 m = n - 1，则可从任一度数为1的点搜索即可；
2）若 m = n，多余的一条边连接哈密顿路径上的两点，从任一度数为1的点搜索即可。
3）若不存在度数为1的点，从任一点开始搜索。
复杂度O(n)。
1 #include2 #include 3 #include 4 5 using namespace std; 6 7 const int maxn = 1e3 + 10; 8 9 struct Edge{10 int to, next;11 }edge[2 * maxn];12 13 int n, d1, d0, N, S;14 bool vis[maxn], ans;15 int d[maxn], head[maxn];16 17 void addEdge(int u, int v){18 edge[N].next = head[u];19 edge[N].to = v;20 head[u] = N++;21 }22 23 bool inMap(int u, int v){24 for(int i = head[u]; i + 1; i = edge[i].next){25 int v1 = edge[i].to;26 if(v1 == v) return 1;27 }28 return 0;29 }30 31 bool dfs(int u, int cnt){32 if(cnt == n) return ans = 1;33 if(ans) return 1;34 for(int i = head[u]; i + 1; i = edge[i].next){35 int v = edge[i].to;36 if(vis[v]) continue;37 vis[v] = 1;38 dfs(v, cnt + 1);39 vis[v] = 0;40 }41 }42 43 int main(){44 while(~scanf("%d", &n)){45 memset(d, 0, sizeof d);46 memset(head, -1, sizeof head);47 N = 0;48 for(int i = 0, u, v; i < n; i++){49 scanf("%d%d", &u, &v);50 if(u != v && !inMap(u, v)){51 addEdge(u, v);52 addEdge(v, u);53 ++d[u], ++d[v];54 }55 }56 d0 = d1 = 0;57 S = 1;58 for(int i = 1; i <= n; i++){59 if(!d[i]) ++d0;60 else if(d[i] == 1){61 ++d1;62 S = i;63 }64 }65 if(d0 + d1 > 2){66 puts("NO");67 continue;68 }69 ans = 0;70 memset(vis, 0, sizeof vis);71 vis[S] = 1;72 dfs(S, 1);73 puts(ans ? "YES" : "NO");74 }75 return 0;76 }