Maximum Employees to Be Invited to a Meeting LeetCode solution in Python

1
class Solution:
2
    def maximumInvitations(self, favorite: List[int]) -> int:
3
        n = len(favorite)
4
        visited_time = [0] * n
5
        inpath = [False] * n
6
        cur_time = 1
7

8
        def get_max_len_cycle(cur):
9
            nonlocal cur_time
10
            inpath[cur], visited_time[cur], nxt = True, cur_time, favorite[cur]
11
            cur_time += 1
12
            ret = 0 if not inpath[nxt] else visited_time[cur] - visited_time[nxt] + 1
13
            if visited_time[nxt] == 0:
14
                ret = max(ret, get_max_len_cycle(nxt))
15
            inpath[cur] = False
16
            return ret
17

18
        ret_cycle = 0
19
        for i in range(n):
20
            if visited_time[i] == 0:
21
                ret_cycle = max(ret_cycle, get_max_len_cycle(i))
22

23
        ret_not_cycle = 0
24
        back_edge_graph = [[] for _ in range(n)]
25
        for i in range(n):
26
            back_edge_graph[favorite[i]].append(i)
27

28
        def get_max_depth(cur):
29
            ret = 0
30
            for nxt in back_edge_graph[cur]:
31
                if favorite[cur] != nxt:
32
                    ret = max(ret, get_max_depth(nxt) + 1)
33
            return ret
34

35
        for i in range(n):
36
            if favorite[favorite[i]] == i:
37
                ret_not_cycle += get_max_depth(i) + 1
38

39
        ret = max(ret_cycle, ret_not_cycle)
40
        return ret