这个题太长了……但是解法又出奇的水。 有兴趣的读原文去，我还是把题目化简一下比较好。M个节点的无向图，M是偶数。这个无向图是这么来的，首先它是树，然后这个树的节点要么只和一个节点相连，要么和 3个节点相连…… 度为1的是叶子，我们把一个叶子当做根，拎上去……，那么度为3的是二叉树的中间节点。所有的节点要么是叶子，要么有两个孩子，就是这么一个特殊的树。然后把所有的叶子按顺序连称一个圈包括我们规定的根）。问最终形成的图，有多少条哈密尔顿回路。问题的输入是原来那个树的dfs序列……M是节点数的话 输入长度N = 2 *( M - 1)范围在[4..200000]，数组里的元素大小是[0..(M-1)]。
输出要求：
如果哈密尔顿圈的数超过10^8，输出-1。
如果输入非法，输出-2。
合法性： （1） 每条路连接两个不同的节点
（2） 每个节点经过一次或者3次。
（3） 每条路走了两次
复杂度要求：时间O(N)，空间O(N)。
分析： 首先合法性判断是说判断给定的那个dfs序列是不是一棵满足要求的树，我们自己弄个堆栈判断一下就好了，O(N)。这个题的时间复杂度就在这里，空间复杂度也在这里。但是这个题最难的不在这里……，最难的在于哈密尔顿圈的个数。
我曾经看了一个分析挺好的。。。。
红得表示经过，A是父亲，B C是子树，总之就是孩子的走法决定了上层的走法也唯一，然后这个子树考虑完之后可以缩成点……
总之，无论多少个节点，只有3个哈密尔顿圈…… 所以那些输入神马的都是浮云……
代码：
// you can also use includes, for example:
// #include <algorithm>
#include <vector>
int solution(const vector<int> &A) {
// write your code here...
int n = A.size(), m = (n >> 1) + 1,i,invalid = m;
vector<int> num,path;
num.resize(m, 0);
for (i = 0; i < n; ++i) {
if ((i) && (A[i] == A[i - 1])) {
return -2;
}
switch(++num[A[i]]) {
case 1:
path.push_back(A[i]);
--invalid;
break;
case 2:
if ((path.size() < 2) || (path[path.size() - 2] != A[i])) {
return -2;
}
++invalid;
path.pop_back();
break;
case 3:
if ((path.size() < 2) || (path[path.size() - 2] != A[i])) {
return -2;
}
--invalid;
path.pop_back();
break;
default:
return -2;
}
}
return invalid?(-2):3;
}