首页 > 编程语言 >有向图计数优化版原理及C++实现

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

时间:2023-10-19 12:05:17浏览次数:51  
标签:有向图 return cur int C++ vRet 计数 ret next


题目

见前面章节。有向图访问计数的原理及C++实现

第一版

不需要拓扑排序,也不需要并集查找,直接dfs了。完成以下三个职责:
一,DFS那些端点在环上。
二,DFS环上各点此环的长度。
三,DFS非环上各点。

有向图计数优化版原理及C++实现_算法

分析

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++实现资源

doc文档下载:

【免费】闻缺陷则喜之算法册C++实现资源


标签:有向图,return,cur,int,C++,vRet,计数,ret,next
From: https://blog.51cto.com/u_15724537/7934100

相关文章

  • 朴素迪氏最短单源路径的原理及C++实现
    Dijkstra算法,翻译为迪杰斯特拉或狄克斯特拉。在下驽钝,记不住如此长的翻译,故简称迪氏。时间复杂度O(n2),端点数的平方。使用前提边的权为正。可以非连通,非连通的距离为-1。原理源点到源点的最短路径只有一个节点{s}。除源点本身外,其它端点的最短路径至少有两个端点,整个路径{s...x2}可......
  • 有向图访问计数的原理及C++实现
    题目现有一个有向图,其中包含n个节点,节点编号从0到n-1。此外,该图还包含了n条有向边。给你一个下标从0开始的数组edges,其中edges[i]表示存在一条从节点i到节点edges[i]的边。想象在图上发生以下过程:你从节点x开始,通过边访问其他节点,直到你在此过程中再次......
  • Windows下VC++编译器32位memcpy、memmove函数汇编代码详解
    整理者:赤勇玄心行天道QQ号:280604597微信号:qq280604597QQ群:511046632博客:www.cnblogs.com/gaoyaguo  blog.csdn.net/cyz7758520?type=blog大家有什么不明白的地方,或者想要详细了解的地方可以联系我,我会认真回复的!你可以随意转载,无需注明出处!写文档实属不易,我希望大家能支......
  • 深入实践C++11智能指针
    目录概念一、std::auto_ptr二、std::unique_ptr常用函数自定义智能指针对象持有的资源的释放函数三、std::shared_ptr常用函数四、std::enable_shared_from_this五、std::weak_ptr常用函数智能指针使用注意事项智能指针的简单实现概念C/C++语言最为人所诟病的特性之一就是......
  • C++常见入门题题解
    前言因为本人目前比较菜,所以给出的题解都是按照自己的学习进度来的,所以难度是一个循序渐进的过程,由于本人水平有限,望读者能够指出谬误,共同进步。回文数输出#include<bits/stdc++.h>//万能头usingnamespacestd;intmain(void){vector<int>font;//定义一个整型的向......
  • C++模板笔记
    参考文章:https://juejin.cn/post/7078530622527897631模板是C++的泛型编程机制,这种机制可以最大程度复用代码并且不会增加运行时开销模板分为函数模板和类模板函数模板函数模板是对函数的参数进行泛型化,传递给模板函数的类型实参可以是类,也可以是整型值,还可以是模板名比如://......
  • Qt/C/C++ 项目工程架构搭建设计经验
    摘要  独立负责一个Qt项目和经过前辈的教导后的一些架构搭建感悟,其中的各种理念对其他语言开发的项目也能有一定的互通,能带来更舒适的开发体验,谨代表个人开发的经验之谈,有需要的小伙伴酌情获取,辩证思考。也欢迎小伙伴们在评论区纠错补充。  关键词:C/C++、Qt、搭建框架、更......
  • 关于 K 维空间中整点之间曼哈顿距离最短路径计数问题
    约定\(K\)维空间中,整点的坐标以\(K\)个整数表示,形如\[Point\left(X_1,X_2,\cdots,X_k\right)\]定义两个点的曼哈顿距离为每一维坐标差的绝对值之和,记为\[MD\left(A,B\right)=\sum_{i=1}^{K}\left|{X_{i_A}-X_{i_B}}\right|\]定义两个点\(A\),\(B\)相邻当且仅当......
  • 您需要了解的有关下一个MISRA®标准的信息:MISRA C++ 2023®简介
    我们在直播课中讲解过MISRAC通识及实践(请看VCR),今天我们来探讨一下MISRAC++:2023~ 【北汇信息|MISRAC通识及实践】 MISRAC++:2023®是广受期待的MISRAC++®标准的下一个版本,将于今年晚些时候发布。新版本将整合AUTOSARC++14指南,并支持C++的最新版本。 MISRA®是......
  • 学习C++
    概述:C++的基础语法主要包括变量、常量、数据类型、运算符、控制流语句等。下面分别进行介绍。变量和常量:变量是程序中用于存储数据的标识符,可以改变其值。在C++中,变量必须先声明后使用,声明的语法格式为“数据类型变量名”。例如,声明一个整型变量:inta。常量是在程序中不能改变......