C++深度优先搜索(DFS)算法的应用：树中可以形成回文的路径数

class Solution {
public:
long long countPalindromePaths(vector& parent, string s) {
m_c = parent.size();
m_str = s;
m_vNeiBo.assign(m_c, vector());
for (int i = 0; i < 26; i++)
{
m_iVilidMask[i] = 1 << i;
}
m_llRet = 0;
int iRoot = -1;
for (int i = 0; i < m_c; i++)
{
if (-1 == parent[i])
{
iRoot = i;
}
else
{
m_vNeiBo[parent[i]].emplace_back(i);
}
}
std::unordered_map<int, int> mNums;
dfs(iRoot, mNums);
return m_llRet ;
}
void dfs(int cur, std::unordered_map<int, int>& mNums)
{
const int curMask = 1 << (m_str[cur] - ‘a’);
mNums[curMask]++;
for (const auto& child : m_vNeiBo[cur])
{
std::unordered_map<int, int> childNums;
dfs(child, childNums);
ChangeNum(mNums, childNums,curMask);
for (const auto& it : childNums)
{
mNums[it.first ^ curMask] += it.second;
}
}
}
void ChangeNum(const std::unordered_map<int, int>& mNums, const std::unordered_map<int, int>& childNums, const int curMask )
{
for (const auto& it : childNums)
{
for (int i = 0; i < 27; i++)
{
const int iNeedMask = it.first ^ m_iVilidMask[i] ^ curMask;
if (mNums.count(iNeedMask))
{
m_llRet += (long long)it.second * mNums.find(iNeedMask)->second;
}
}
}
}
//状态压缩 1表示z是奇数数量,2表示y是奇数数量,3表示yz都是奇数数量
int m_iVilidMask[27] = { 0 };//记录所有字符都是偶数和只有一个字符是奇数
vector<vector> m_vNeiBo;
//vector m_vNums;
int m_c;
long long m_llRet = 0;//不包括单节点的合法路径数
string m_str;
};

template
void Assert(const vector& v1, const vector& v2)
{
if (v1.size() != v2.size())
{
assert(false);
return;
}
for (int i = 0; i < v1.size(); i++)
{
Assert(v1[i], v2[i]);
}
}
int main()
{
Solution slu;
vector parent;
long long res;
string s;
parent = { -1 };
s = “a”;
res = slu.countPalindromePaths(parent, s);
Assert(res, 0LL);
parent = { -1,0 };
s = “aa”;
res = slu.countPalindromePaths(parent, s);
Assert(res, 1LL);
parent = { -1,0,1 };
s = “aaa”;
res = slu.countPalindromePaths(parent, s);
Assert(res, 3LL);
parent = { -1,0,0 };
s = “aaa”;
res = slu.countPalindromePaths(parent, s);
Assert(res, 3LL);
parent = { -1,0,0 };
s = “aba”;
res = slu.countPalindromePaths(parent, s);
Assert(res,2LL);
parent = { -1,0,0 };
s = “baa”;
res = slu.countPalindromePaths(parent, s);
Assert(res, 3LL);
parent = { -1,0,0,1,1,2 };
s = “acaabc”;
res = slu.countPalindromePaths(parent, s);
Assert(res, 8LL);
parent = { -1, 0, 0, 0, 0 };
s = “aaaaa”;
res = slu.countPalindromePaths(parent, s);
Assert(res, 10LL);