基环树学习指南

前置芝士

一个图中包含n个点n条边，且图中只存在一个环，这样的图被称为基环树（环套树）。

基环树比树多了一条边，从而形成了一个环。基环树可以看做以坏点为根的一颗颗子树构成。

三大分类

基环无向树

基环内向树（每个点有且只有一条出边）

基环外向树（每一个点只有一条入边）

[解题步骤]

深搜找环。

断环成树，对树深搜计算。

保证这 (n) 个点 (n) 条边构成的是一个连通图时有唯一环。

如果图不连通但是每个联通块点数都等于边数时，这个图就是一个基环树森林。

基环内向树访问计数

[problem description]

现有一个有向图，其中包含 n 个节点，节点编号从 0 到 n - 1 。此外，该图还包含了 n 条有向边。

给你一个下标从 0 开始的数组 edges ，其中 edges[i] 表示存在一条从节点 i 到节点 edges[i] 的边。

• 你从节点 x 开始，通过边访问其他节点，直到你在此过程中再次访问到之前已经访问过的节点。
• 返回数组 answer 作为答案，其中 answer[i] 表示如果从节点 i 开始执行该过程，你可以访问到的不同节点数。
• 2<=n<= 10^5

[solved]

（1）反向建边，更有利于将树枝删去。

（2）拓扑排序，剪掉 图上的所有树枝，deg 值为 1 的点必定在基环上，为 0 的点必定在树枝上。

（3）dfs，需要考虑节点不在一个连通块里。

[python]

class Solution:
    def countVisitedNodes(self, edges: List[int]) -> List[int]:
        n=len(edges)
        rg=[[]for _ in range(n)] #反图
        deg=[0]*n #统计出度
        for x,y in enumerate(edges):
            rg[y].append(x)
            deg[y]+=1
        # 拓扑排序，剪掉 g 上的所有树枝
        # 拓扑排序后，deg 值为 1 的点必定在基环上，为 0 的点必定在树枝上
        q=deque()
        for i in range(n):
            if deg[i]==0:
                q.append(i)
        while q:
            u=q.popleft()
            v=edges[u]
            deg[v]-=1
            if deg[v]==0:  # 树枝上的点在拓扑排序后，入度均为 0
                q.append(v)
        ans=[0]*n
         # 在反图上遍历树枝
        def dfs(x:int,depth:int)->None:
            ans[x]=depth
            for v in rg[x]:
                if deg[v]==0:
                    dfs(v,depth+1)   
        for i,x in enumerate(deg):
            if x<=0:
                continue
            ring=[]
            v=i
            while True:
                deg[v]=-1   # 将基环上的点的入度标记为 -1，避免重复访问
                ring.append(v)  # 收集在基环上的点
                v=edges[v]
                if v==i:
                    break
            for i in ring:
                dfs(i,len(ring))  # 为方便计算，以 len(ring) 作为初始深度
        return ans