备案号新增网站,李光辉:营销型企业网站建设的指导思想是什么?,asp网站管理系统,网站框架是谁做题目
现有一个有向图#xff0c;其中包含 n 个节点#xff0c;节点编号从 0 到 n - 1 。此外#xff0c;该图还包含了 n 条有向边。 给你一个下标从 0 开始的数组 edges #xff0c;其中 edges[i] 表示存在一条从节点 i 到节点 edges[i] 的边。 想象在图上发生以下过程其中包含 n 个节点节点编号从 0 到 n - 1 。此外该图还包含了 n 条有向边。 给你一个下标从 0 开始的数组 edges 其中 edges[i] 表示存在一条从节点 i 到节点 edges[i] 的边。 想象在图上发生以下过程 你从节点 x 开始通过边访问其他节点直到你在 此过程 中再次访问到之前已经访问过的节点。 返回数组 answer 作为答案其中 answer[i] 表示如果从节点 i 开始执行该过程你可以访问到的不同节点数。 2 n 100000 无自环。
原理分析
如果只有一个连通区域则有且只有一环。反证法假定没有环除源点外还可以到达n个端点共n1个端点与共有n个端点重复。假定有x个环则不重复端点数为1n-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; } vectorint m_vCycle; }; class Solution { public: vectorint countVisitedNodes(vectorint edges) { m_c edges.size(); vectorvectorint 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_mapint, 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 vectorint edges) { if (-1 ! m_vDis[cur]) { return m_vDis[cur]; } return m_vDis[cur] dfs(edges[cur], edges) 1; } vectorint m_vDis; CTestTS m_ts; int m_c; };
测试用代码
int main() { vectorint edges { 1,2,3,4,0 }; //vectorint edges { 1,2,0,0 }; Solution slu; auto res slu.countVisitedNodes(edges); }
测试环境
Win10 VS2022 C17
相关下载
源码可直接运行
https://download.csdn.net/download/he_zhidan/88388717
doc格式方便查阅
【免费】闻缺陷则喜之算法册C实现资源-CSDN文库
更多算法见
结构与算法_闻缺陷则喜何志丹的博客-CSDN博客
