见前面章节。有向图访问计数的原理及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
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版
https://download.csdn.net/download/he_zhidan/88348653
作者人生格言 |
有所得,以墨记之,故曰墨家 |
闻缺陷则喜。问题发现得越早,越给老板省钱。 |
算法是程序的灵魂 |