题解-有向图访问计数,一个有向基环树的简单应用

> Problem: 2876. 有向图访问计数

思路

– 注意到这个图一定有环,而且每个点的出度都为1

– 由题意可知从任意节点出发其都能访问到相关的环

– 答案只分为两个情况:

    – 点在环上,此时能访问的点只有环上的点,不可能出环,答案为环的长度

    – 点在环外,除了环本身之外,其能访问本节点到环的几个节点,答案为环的长度加上其到环的距离

– 注意到可能有多个环相互独立存在,但是不可能出现两个环连通,所以几个图之间互相并不干扰

解题方法

1. 由以上思路得到基本想法,遍历解决每一个单独的环即可

2. 选择一个没有访问的节点,开始访问,其一定能进入环

    1. 记录初次访问访问点的深度

    2. 判断是否已经入环的方法就是判断该节点是否已经访问过

3. 对于当前点已经访问过有两种情况:

    1. 当前节点在之前的旧图上就访问过:此时根据访问深度加上之前已经得出点的答案来更新答案数组

    2. 当前节点是在这个新图上访问两次:此时第二次访问深度减去节点访问深度就是环的长度,更新环上节点的答案,环外带上的节点根据访问深度加环的长度更新

4. 持续上述操作直到所有节点都访问过,因为我们每次都将单个有环图的所有节点处理,所以每个节点都已经处理

> 时间复杂度,$O(n)$

> 空间复杂度,$O(n)$

代码

,对于这种问题应该可以补一个快慢指针法,但是此处没有做

class Solution:
    def countVisitedNodes(self, edges: List[int]) -> List[int]:
        n=len(edges)
        res=[-1]*n
        visited=set()
        for i in range(n):
            if i in visited:
                continue
            now=begin=i #记录begin就不用做反图,直接顺序遍历就能找到答案
            tmp=dict()#记录此次遍历的时候访问的点
            index=0
            while now not in visited:
                tmp[now]=index
                visited.add(now)
                index+=1
                now=edges[now]
            # 此时我们访问了的图有三种可能,一条带,一个环,一个有带的环
            # 后两种可能都是如下解法
            if now in tmp:
                #此时tmp[now]长度为点到环的长度
                belt=dict()
                circle=set()
                length=tmp[now]
                now=begin
                while length>0:
                    belt[now]=length
                    length-=1
                    now=edges[now]
                while now not in circle:
                    circle.add(now)
                    now=edges[now]
                r=len(circle)#环的长度
                for u in tmp:
                    res[u]=r if u in circle else r+belt[u]
            # 第一种可能是比较好处理的
            else:
                #说明连接到了之前的有向基环树上,直接与已经访问的点相加即可
                length=index
                baseLength=res[now]
                now=begin
                while length>0:
                    res[now]=baseLength+length
                    now=edges[now]
                    length-=1
    return res</code></pre>