有向图访问计数的原理及C++实现

题目

现有一个有向图，其中包含 n 个节点，节点编号从 0 到 n - 1 。此外，该图还包含了 n 条有向边。
给你一个下标从 0 开始的数组 edges ，其中 edges[i] 表示存在一条从节点 i 到节点 edges[i] 的边。
想象在图上发生以下过程：
你从节点 x 开始，通过边访问其他节点，直到你在 此过程 中再次访问到之前已经访问过的节点。
返回数组 answer 作为答案，其中 answer[i] 表示如果从节点 i 开始执行该过程，你可以访问到的不同节点数。
2 <= n <= 100000
无自环。

原理分析

如果只有一个连通区域，则有且只有一环。反证法：假定没有环，除源点外，还可以到达n个端点，共n+1个端点，与共有n个端点重复。假定有x个环，则不重复端点数为：1+n-x。当且仅当x为1是，不重复端点数为n。
当有多个连通区域时，任何一个连通区域都有且只有一个环。下面分两步来证明：一，此连通区域必定有环。二，此区域不存在两个或更多的环。
假定此区域的一条边为i0->edges[i0]，edges[i0]简称为i1。如果没有环， 则edges[i1](简称为i2)也在此连通区域，edges[i2](简称i3)也在此连通区域,i4.... 。此连通区域的点数无限，和端点数小于等于n矛盾。
由于出度为1，所以进入环后，无法离开环。自然没第二个环。

编码思路

根据拓扑排序，发现那些点在环上。
根据并集查找获取各连通区域。
统计各连通区域在环上的点数。
求环上各点可以到达的点数，就是此环长度(端点数）。
DFS非环上各点可以到达的点数。就是到环的距离+此环的长度。
拓扑排序和并集查找已经封装，可以直接使用。

核心源码

class CTestTS : public CTopSort
 {
 public:
     // 通过 CTopSort 继承
     virtual void OnDo(int pre, int cur) override
     {
         m_vCycle[cur] = false;
     }
     vector<int> m_vCycle;
 };
 class Solution {
 public:
     vector<int> countVisitedNodes(vector<int>& edges) {
         m_c = edges.size();
         vector<vector<int>> vNeiB(m_c);
         CUnionFind uf(m_c);
         for (int i = 0; i < edges.size(); i++)
         {
             vNeiB[i].emplace_back(edges[i]);
             uf.Union(i, edges[i]);
         }
         
         m_ts.m_vCycle.assign(m_c, true);        
         m_ts.Init(vNeiB);
         m_vDis.resize(m_c, -1);
         //环可能处于不同的联通区域
         std::unordered_map<int, int> mRegionNode;//各联通区域环的端点数
         for (int i = 0; i < m_c; i++)
         {
             if (m_ts.m_vCycle[i])
             {
                 mRegionNode[uf.GetConnectRegionIndex(i)]++;
             }
         }
         for (int i = 0; i < m_c; i++)
         {
             if (m_ts.m_vCycle[i])
             {
                 m_vDis[i] = mRegionNode[uf.GetConnectRegionIndex(i)];
             }
         }
         for (int i = 0; i < m_c; i++)
         {
             dfs(i, edges);
         }        return m_vDis;
     }
     int dfs(int cur,const vector<int>& edges)
     {
         if (-1 != m_vDis[cur])
         {
             return  m_vDis[cur];
         }
         return m_vDis[cur] = dfs(edges[cur], edges) + 1;
     }
     vector<int> m_vDis;
     CTestTS m_ts;
     int m_c;
 };

测试用代码

int main()
 {
     vector<int> edges = { 1,2,3,4,0 };
     //vector<int> edges = { 1,2,0,0 };
     Solution slu;
     auto res = slu.countVisitedNodes(edges);
 }

测试环境

Win10 +VS2022 + C++17

相关下载

源码：可直接运行

doc格式：方便查阅

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

更多算法见：

结构与算法_闻缺陷则喜何志丹的博客