Leetcode: 2127. Maximum Employees to Be Invited to a Meeting

Mistake: Missing edge case. Failed to recognize that the solution is either a cycle of a sum of paths.
Can we break-down the problem in small and easily to solve parts? Clearly, one possible solution is to find the Longest Cycle in a Directed Graph. Otherwise, we can seat groups of people that where their favorite chain ends on two people that would like to seat besides each other. Time complexity is \(O(n)\) and space is \(O(n)\).

from typing import List
from collections import defaultdict


class Solution:
    def maximumInvitations(self, e: List[int]) -> int:
        N = len(e)

        re = defaultdict(list)
        for u, v in enumerate(e):
            if e[v] != u:
                re[v].append(u)

        def find_longest_path(u, seen):
            if longest_path[u] is not None:
                return longest_path[u]
            seen.add(u)
            ans = 1
            for v in re[u]:
                ans = max(ans, 1 + find_longest_path(v, seen))
            longest_path[u] = ans
            return ans

        longest_path = [None] * N
        ans = 0
        seen = set()
        for u, v in enumerate(e):
            if e[v] == u and u < v:
                ans += find_longest_path(u, seen) + find_longest_path(v, seen)

        found_at = [None] * N

        def find_longest_cycle(u, k, seen):
            seen.add(u)
            found_at[u] = k
            v = e[u]
            if v in seen:
                ans = ((k + 1) - found_at[v]) if found_at[v] is not None else 0
            else:
                ans = find_longest_cycle(v, k + 1, seen)
            found_at[u] = None
            return ans

        seen = set()
        for u in range(N):
            if u not in seen:
                ans = max(ans, find_longest_cycle(u, 0, seen))
        return ans


assert Solution().maximumInvitations([2, 2, 1, 2]) == 3
assert Solution().maximumInvitations([1, 2, 0]) == 3
assert Solution().maximumInvitations([3, 0, 1, 4, 1]) == 4