• 有向图计数优化版原理及C++实现


    题目

    见前面章节。有向图访问计数的原理及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


    核心代码

    1. class Solution {
    2. public:
    3.     vector<int> countVisitedNodes(vector<int>& edges) {
    4.         m_c = edges.size();
    5.         m_edges = edges;
    6.         m_vRet.assign(m_c, -1);
    7.         for (int i = 0; i < m_c; i++)
    8.         {
    9.             std::unordered_map<int, int> mPreNO;
    10.             dfs(i, mPreNO, 1);
    11.         }
    12.         return m_vRet;
    13.     }
    14.     int dfs(int cur,std::unordered_map<int,int>& mPreNO,int iNO)
    15.     {
    16.         if (mPreNO.count(cur))
    17.         {
    18.             m_vRet[cur] = iNO - mPreNO[cur];
    19.             return cur;
    20.         }
    21.         mPreNO[cur] = iNO;
    22.         const auto& next = m_edges[cur];
    23.         const int iRet = dfs(next, mPreNO, iNO + 1);
    24.         if (iRet == cur)
    25.         {
    26.             return -1;//环结束了
    27.         }
    28.         if (-1 == iRet)
    29.         {
    30.             m_vRet[cur] = m_vRet[next]+1;
    31.         }
    32.         else
    33.         {
    34.             m_vRet[cur] = m_vRet[next];
    35.         }
    36.         return iRet;
    37.     }
    38.     vector<int> m_vRet;
    39.     vector<int> m_edges;
    40.     int m_c;
    41. };

    记忆化


    如果ret[cur]不为-1,说明cur已经处理。如果cur是环上一点,那说明整个环已经处理,返回-1;如果cur,不是环上一点,也返回-1。


    时间复杂度


    O(n),任意端点,dfs最多执行两次,一次是主动执行,一次是作为出边被执行。

    优化后的代码

    1. class Solution {
    2. public:
    3.     vector<int> countVisitedNodes(vector<int>& edges) {
    4.         m_c = edges.size();
    5.         m_edges = edges;
    6.         m_vRet.assign(m_c, -1);
    7.         for (int i = 0; i < m_c; i++)
    8.         {
    9.             std::unordered_map<int, int> mPreNO;
    10.             dfs(i, mPreNO, 1);
    11.         }
    12.         return m_vRet;
    13.     }
    14.     int dfs(int cur,std::unordered_map<int,int>& mPreNO,int iNO)
    15.     {
    16.         if (-1 != m_vRet[cur])
    17.         {
    18.             return -1;
    19.         }
    20.         if (mPreNO.count(cur))
    21.         {
    22.             m_vRet[cur] = iNO - mPreNO[cur];
    23.             return cur;
    24.         }
    25.         mPreNO[cur] = iNO;
    26.         const auto& next = m_edges[cur];
    27.         const int iRet = dfs(next, mPreNO, iNO + 1);
    28.         if (iRet == cur)
    29.         {
    30.             return -1;//环结束了
    31.         }
    32.         if (-1 == iRet)
    33.         {
    34.             m_vRet[cur] = m_vRet[next]+1;
    35.         }
    36.         else
    37.         {
    38.             m_vRet[cur] = m_vRet[next];
    39.         }
    40.         return iRet;
    41.     }
    42.     vector<int> m_vRet;
    43.     vector<int> m_edges;
    44.     int m_c;
    45. };

    再次优化后的代码

    用数组代替哈希映射,速度似乎没提升。

    1. class Solution {
    2. public:
    3.     vector<int> countVisitedNodes(vector<int>& edges) {
    4.         m_c = edges.size();
    5.         m_edges = edges;
    6.         m_vRet.assign(m_c, -1);
    7.         int vPreNO[100000];
    8.         for (int i = 0; i < m_c; i++)
    9.         {
    10.             vPreNO[i] = -1;
    11.         }
    12.         for (int i = 0; i < m_c; i++)
    13.         {
    14.             dfs(i, vPreNO, 1);
    15.         }
    16.         return m_vRet;
    17.     }
    18.     int dfs(int cur,int* vPreNO,int iNO)
    19.     {
    20.         if (-1 != m_vRet[cur])
    21.         {
    22.             return -1;
    23.         }
    24.         if (-1 != vPreNO [cur])
    25.         {
    26.             m_vRet[cur] = iNO - vPreNO[cur];
    27.             return cur;
    28.         }
    29.         vPreNO[cur] = iNO;
    30.         const auto& next = m_edges[cur];
    31.         const int iRet = dfs(next, vPreNO, iNO + 1);
    32.         if (iRet == cur)
    33.         {
    34.             return -1;//环结束了
    35.         }
    36.         if (-1 == iRet)
    37.         {
    38.             m_vRet[cur] = m_vRet[next]+1;
    39.         }
    40.         else
    41.         {
    42.             m_vRet[cur] = m_vRet[next];
    43.         }
    44.         return iRet;
    45.     }
    46.     vector<int> m_vRet;
    47.     vector<int> m_edges;
    48.     int m_c;
    49. };

    注意


    如果用vector记录PreNO,则需要在for循环外初始化,如果for循环内初始化,则时间复杂度变为O(n*n)。

    测试环境

    VS2022 Win10 C++17

    下载

    源码下载:

    【免费】.有向图计数优化版原理及C++实现资源-CSDN文库

    https://img-blog.csdnimg.cn/ea2601b3918f4aef836b5fe30da2ebf7.gif#pic_center#pic_center

    其它

    视频课程

    如果你觉得复杂,想从简单的算法开始,可以学习我的视频课程。

    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

    作者人生格言

    有所得,以墨记之,故曰墨家

    闻缺陷则喜。问题发现得越早,越给老板省钱。

    算法是程序的灵魂

    https://img-blog.csdnimg.cn/f95ddae62a4e43a68295601c723f92fb.gif#pic_center

  • 相关阅读:
    NLP-词向量、Word2vec
    差分代码模板
    信息学奥赛一本通 1361:产生数(Produce)
    距离相关系数的原理及其实现(Numpy代码+第三方包的实现)
    系统集成测试(SIT)/系统测试(ST)/用户验收测试(UAT)
    多肽介导PEG磷脂——靶向功能材料之DSPE-PEG-RGD/TAT/NGR/APRPG
    2023年【R2移动式压力容器充装】模拟考试及R2移动式压力容器充装模拟考试题
    AI:业余时间打比赛—挣它个小小目标—【阿里安全×ICDM 2022】大规模电商图上的风险商品检测比赛
    轻松掌握组件启动之MongoDB(番外篇):高可用复制集架构环境搭建-mtools
    Go 语言中的反射
  • 原文地址:https://blog.csdn.net/he_zhidan/article/details/133496448