题目
见前面章节。有向图访问计数的原理及C++实现-CSDN博客
第一版
不需要拓扑排序，也不需要并集查找，直接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
下载
源码下载：
【免费】.有向图计数优化版原理及C++实现资源-CSDN文库
其它
视频课程
如果你觉得复杂，想从简单的算法开始，可以学习我的视频课程。
https://edu.csdn.net/course/detail/38771
我的其它课程
https://edu.csdn.net/lecturer/6176
测试环境
win7 VS2019 C++17 或Win10 VS2022 Ck++17
相关下载
算法精讲《闻缺陷则喜算法册》doc版
