<p>A company is organizing a meeting and has a list of <code>n</code> employees, waiting to be invited. They have arranged for a large <strong>circular</strong> table, capable of seating <strong>any number</strong> of employees.</p>

<p>The employees are numbered from <code>0</code> to <code>n - 1</code>. Each employee has a <strong>favorite</strong> person and they will attend the meeting <strong>only if</strong> they can sit next to their favorite person at the table. The favorite person of an employee is <strong>not</strong> themself.</p>

<p>Given a <strong>0-indexed</strong> integer array <code>favorite</code>, where <code>favorite[i]</code> denotes the favorite person of the <code>i<sup>th</sup></code> employee, return <em>the <strong>maximum number of employees</strong> that can be invited to the meeting</em>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2021/12/14/ex1.png" style="width: 236px; height: 195px;" />
<pre>
<strong>Input:</strong> favorite = [2,2,1,2]
<strong>Output:</strong> 3
<strong>Explanation:</strong>
The above figure shows how the company can invite employees 0, 1, and 2, and seat them at the round table.
All employees cannot be invited because employee 2 cannot sit beside employees 0, 1, and 3, simultaneously.
Note that the company can also invite employees 1, 2, and 3, and give them their desired seats.
The maximum number of employees that can be invited to the meeting is 3. 
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> favorite = [1,2,0]
<strong>Output:</strong> 3
<strong>Explanation:</strong> 
Each employee is the favorite person of at least one other employee, and the only way the company can invite them is if they invite every employee.
The seating arrangement will be the same as that in the figure given in example 1:
- Employee 0 will sit between employees 2 and 1.
- Employee 1 will sit between employees 0 and 2.
- Employee 2 will sit between employees 1 and 0.
The maximum number of employees that can be invited to the meeting is 3.
</pre>

<p><strong class="example">Example 3:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2021/12/14/ex2.png" style="width: 219px; height: 220px;" />
<pre>
<strong>Input:</strong> favorite = [3,0,1,4,1]
<strong>Output:</strong> 4
<strong>Explanation:</strong>
The above figure shows how the company will invite employees 0, 1, 3, and 4, and seat them at the round table.
Employee 2 cannot be invited because the two spots next to their favorite employee 1 are taken.
So the company leaves them out of the meeting.
The maximum number of employees that can be invited to the meeting is 4.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>n == favorite.length</code></li>
	<li><code>2 &lt;= n &lt;= 10<sup>5</sup></code></li>
	<li><code>0 &lt;= favorite[i] &lt;=&nbsp;n - 1</code></li>
	<li><code>favorite[i] != i</code></li>
</ul>

from typing import List

class Solution:
    def maximumInvitations(self, favorite: List[int]) -> int:
        N = len(favorite)
        # m[i] keeps track of the depth of node i. -1 means unvisited.
        depth = [-1] * N
        # Reverse graph: each employee has a list of employees that like them.
        reverse_graph = [[] for _ in range(N)]
        
        # Build the reverse graph
        for i in range(N):
            reverse_graph[favorite[i]].append(i)
        
        # DFS to calculate the depth of a node's subtree in the reverse graph
        def find_depth(employee: int) -> int:
            if depth[employee] != -1:
                return depth[employee]
            max_depth = 0
            for next_employee in reverse_graph[employee]:
                max_depth = max(max_depth, find_depth(next_employee))
            depth[employee] = 1 + max_depth
            return depth[employee]

        max_cycle_size = 0
        free_chain_size = 0
        
        # Case 1: Handling mutual favorite pairs and their free chains
        for i in range(N):
            if depth[i] != -1:
                continue
            
            # Check if employee i and their favorite form a mutual pair
            if favorite[favorite[i]] == i:
                # Mark the mutual pair as visited
                depth[i] = depth[favorite[i]] = 0
                
                # Find the longest chains extending from the mutual pair
                longest_chain_from_i = 0
                for next_employee in reverse_graph[i]:
                    if next_employee != favorite[i]:
                        longest_chain_from_i = max(longest_chain_from_i, find_depth(next_employee))
                
                longest_chain_from_favorite_i = 0
                for next_employee in reverse_graph[favorite[i]]:
                    if next_employee != i:
                        longest_chain_from_favorite_i = max(longest_chain_from_favorite_i, find_depth(next_employee))
                
                # The size of this free component is the two longest chains plus the mutual pair
                free_chain_size += longest_chain_from_i + longest_chain_from_favorite_i + 2

        # Case 2: Handling cycles
        def find_cycle(employee: int):
            if depth[employee] != -1:
                # If already visited, return the entry point of the cycle and depth
                return (employee, depth[employee], False)
            
            depth[employee] = 0
            entry_point, cycle_depth, cycle_found = find_cycle(favorite[employee])
            
            if cycle_found:
                return (entry_point, cycle_depth, True)
            
            depth[employee] = cycle_depth + 1
            return (entry_point, depth[employee], employee == entry_point)

        # Process all nodes to detect cycles
        for i in range(N):
            if depth[i] != -1:
                continue
            entry_point, cycle_depth, cycle_found = find_cycle(i)
            if cycle_found:
                max_cycle_size = max(max_cycle_size, cycle_depth)
        
        # The result is the maximum of either the longest cycle or the largest free component
        return max(max_cycle_size, free_chain_size)

59100