做示意图的网站,互联网网站开发,手机下载app的软件,战队logo设计在线生成给一个n个节点n条边的无向图G#xff0c;试判断图中是否存在哈密顿路径。 若G中存在哈密顿路径l#xff0c;则路径端点度数不小于1#xff0c;其余点度数不小于2。 则G存在哈密顿路径的必要条件#xff1a; 1#xff09;G连通#xff1b; 2#xff09;G中度数为1的点不超…给一个n个节点n条边的无向图G试判断图中是否存在哈密顿路径。 若G中存在哈密顿路径l则路径端点度数不小于1其余点度数不小于2。 则G存在哈密顿路径的必要条件 1G连通 2G中度数为1的点不超过两个。 考虑到简单连通图中边的数目m不超过n 1若 m n - 1则可从任一度数为1的点搜索即可 2若 m n多余的一条边连接哈密顿路径上的两点从任一度数为1的点搜索即可。 3若不存在度数为1的点从任一点开始搜索。 复杂度O(n)。 http://acm.hdu.edu.cn/showproblem.php?pid5424 1 #include cstdio2 #include cstring3 #include algorithm4 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 } View Code 转载于:https://www.cnblogs.com/astoninfer/p/4783789.html
