题目
见前面章节。有向图访问计数的原理及C++实现
第一版
不需要拓扑排序，也不需要并集查找，直接dfs了。完成以下三个职责：
一，DFS那些端点在环上。
二，DFS环上各点此环的长度。
三，DFS非环上各点。
分析
cur是当前dfs的节点，next为edges[cur]。从后向前分析：
判定处理
|
|
ret的值 |
返回值 |
|
找到环尾 |
ret [cur] = NO - mPreNO[cur] |
cur |
|
找到环尾，没找到环首 |
ret [cur] = ret [next] |
同dfs(next...) |
|
之前找到环尾和当前环首 |
环尾已处理，无需处理 |
-1 |
|
之前找到首尾 |
ret [cur] = ret [next]+1 |
-1 |
判定表
|
条件一 |
条件二 |
结果 |
|
mPreNO.count(cur) |
无 |
找到环尾 |
|
dfs(next)返回非-1 |
cur不等于dfs(next) |
找到环尾，没找到环首 |
|
cur等于dfs(next) |
之前找到环尾和当前环首 |
|
|
dfs(next)返回非-1 |
|
之前找到首尾 |
|
|
|
|
|
|
DSF0过程 |
|||
|
DFS(0) |
不处理 |
return -1 |
|
|
DFS(1) |
ret[1]=2 |
return 0 |
|
|
DFS(0) |
ret[0]=3-1=2 |
return 0 |
|
|
DFS(1)过程 |
|||
|
DFS(1) |
不处理 |
return -1 |
|
|
DFS(0) |
ret[0]=2 |
return 0 |
|
|
DFS(1) |
ret[1]=3-1=2 |
return 0 |
|
|
FFS(2)过程 |
|||
|
DFS(2) |
ret[2]=3 |
Return -1 |
|
|
DFS(0) |
不处理 |
return -1 |
|
|
DFS(1) |
ret[1]=2 |
return 0 |
|
|
DFS(0) |
ret[0]=3-1=2 |
return 0 |
|
|
FFS(4)过程 |
|||
|
DFS(4) |
ret[4]=3 |
Return -1 |
|
|
DFS(0) |
不处理 |
return -1 |
|
|
DFS(1) |
ret[1]=2 |
return 0 |
|
|
DFS(0) |
ret[0]=3-1=2 |
return 0 |
|
|
FFS(3)过程 |
|||
|
DFS(3) |
Ret[3]=4 |
Return -1; |
|
|
DFS(2) |
ret[2]=3 |
Return -1 |
|
|
DFS(0) |
不处理 |
return -1 |
|
|
DFS(1) |
ret[1]=2 |
return 0 |
|
|
DFS(0) |
ret[0]=3-1=2 |
return 0 |
|
核心代码
class Solution {
public:
vector<int> countVisitedNodes(vector<int>& edges) {
m_c = edges.size();
m_edges = edges;
m_vRet.assign(m_c, -1);
for (int i = 0; i < m_c; i++)
{
std::unordered_map<int, int> mPreNO;
dfs(i, mPreNO, 1);
}
return m_vRet;
}
int dfs(int cur,std::unordered_map<int,int>& mPreNO,int iNO)
{
if (mPreNO.count(cur))
{
m_vRet[cur] = iNO - mPreNO[cur];
return cur;
}
mPreNO[cur] = iNO;
const auto& next = m_edges[cur];
const int iRet = dfs(next, mPreNO, iNO + 1);
if (iRet == cur)
{
return -1;//环结束了
}
if (-1 == iRet)
{
m_vRet[cur] = m_vRet[next]+1;
}
else
{
m_vRet[cur] = m_vRet[next];
}
return iRet;
}
vector<int> m_vRet;
vector<int> m_edges;
int m_c;
};记忆化
如果ret[cur]不为-1，说明cur已经处理。如果cur是环上一点，那说明整个环已经处理，返回-1；如果cur，不是环上一点，也返回-1。
时间复杂度
O(n),任意端点，dfs最多执行两次，一次是主动执行，一次是作为出边被执行。
优化后的代码
class Solution {
public:
vector<int> countVisitedNodes(vector<int>& edges) {
m_c = edges.size();
m_edges = edges;
m_vRet.assign(m_c, -1);
for (int i = 0; i < m_c; i++)
{
std::unordered_map<int, int> mPreNO;
dfs(i, mPreNO, 1);
}
return m_vRet;
}
int dfs(int cur,std::unordered_map<int,int>& mPreNO,int iNO)
{
if (-1 != m_vRet[cur])
{
return -1;
}
if (mPreNO.count(cur))
{
m_vRet[cur] = iNO - mPreNO[cur];
return cur;
}
mPreNO[cur] = iNO;
const auto& next = m_edges[cur];
const int iRet = dfs(next, mPreNO, iNO + 1);
if (iRet == cur)
{
return -1;//环结束了
}
if (-1 == iRet)
{
m_vRet[cur] = m_vRet[next]+1;
}
else
{
m_vRet[cur] = m_vRet[next];
}
return iRet;
}
vector<int> m_vRet;
vector<int> m_edges;
int m_c;
};再次优化后的代码
用数组代替哈希映射，速度似乎没提升。
class Solution {
public:
vector<int> countVisitedNodes(vector<int>& edges) {
m_c = edges.size();
m_edges = edges;
m_vRet.assign(m_c, -1);
int vPreNO[100000];
for (int i = 0; i < m_c; i++)
{
vPreNO[i] = -1;
}
for (int i = 0; i < m_c; i++)
{
dfs(i, vPreNO, 1);
}
return m_vRet;
}
int dfs(int cur,int* vPreNO,int iNO)
{
if (-1 != m_vRet[cur])
{
return -1;
}
if (-1 != vPreNO [cur])
{
m_vRet[cur] = iNO - vPreNO[cur];
return cur;
}
vPreNO[cur] = iNO;
const auto& next = m_edges[cur];
const int iRet = dfs(next, vPreNO, iNO + 1);
if (iRet == cur)
{
return -1;//环结束了
}
if (-1 == iRet)
{
m_vRet[cur] = m_vRet[next]+1;
}
else
{
m_vRet[cur] = m_vRet[next];
}
return iRet;
}
vector<int> m_vRet;
vector<int> m_edges;
int m_c;
};注意
如果用vector<int>记录PreNO，则需要在for循环外初始化，如果for循环内初始化，则时间复杂度变为O(n*n)。
测试环境
VS2022 Win10 C++17
