基环树

模板

一般来说就是先存反图 算入度

然后拓扑排序 剩下的就是基环

第三步 分别对每个基环进行操作 找基环的方式为模板（如下题）

2127. 参加会议的最多员工数 - 力扣（LeetCode）

class Solution:
    def maximumInvitations(self, favorite: List[int]) -> int:
        n = len(favorite)
        deg = [0] * n
        rg = [[] for _ in range(n)]
        for x, y in enumerate(favorite):
            rg[y].append(x)
            deg[y] += 1

        q = deque(i for i, d in enumerate(deg) if d == 0)
        while q:
            x = q.popleft()
            y = favorite[x]
            deg[y] -= 1
            if deg[y] == 0:
                q.append(y)

        def rdfs(x: int) -> int:
            m_depth = 1
            for y in rg[x]:
                if deg[y] == 0:
                    m_depth = max(m_depth, rdfs(y) + 1)
            return m_depth

        
        max_ring_size = sum_chine_size = 0
        # 找基环的套路
        for i, d in enumerate(deg):
            if d <= 0:
                continue
            res = 0
            x = i
            while True:
                res += 1
                deg[x] = -1
                x = favorite[x]
                if x == i:
                    break
            if res == 2:
                sum_chine_size += rdfs(i) + rdfs(favorite[i])
            else:
                max_ring_size = max(max_ring_size, res)
        
        return max(max_ring_size, sum_chine_size)

2876. 有向图访问计数 - 力扣（LeetCode）

class Solution:
    def countVisitedNodes(self, g: List[int]) -> List[int]:
        n = len(g)
        rg = [[] for _ in range(n)]
        deg = [0] * n
        for x, y in enumerate(g):
            rg[y].append(x)
            deg[y] += 1
        
        q = deque(i for i, d in enumerate(deg) if d == 0)
        while q:
            x = q.popleft()
            y = g[x]
            deg[y] -= 1
            if deg[y] == 0:
                q.append(y)
        
        ans = [0] * n

        def rdfs(x, depth):
            ans[x] = depth
            for y in rg[x]:
                if deg[y] == 0:
                    rdfs(y, depth + 1)
		
        # 找基环的操作
        for i, d in enumerate(deg):
            if d <= 0:
                continue
            ring = []
            x = i
            while True:
                ring.append(x)
                deg[x] = -1
                x = g[x]
                if x == i:
                    break
            
            for x in ring:
                rdfs(x, len(ring))
        
        return ans