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

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);
}