<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>

class Solution:
    def maximumInvitations(self, favorite: List[int]) -> int:
        n = len(favorite)
        # we compare two ways and return the larger one
        # 1. form a big cycle, no other person can be added in
        # 2. connect multiple self contained segments
        def find_largest_cycle(favorite):
            max_size = 0
            visited = [False]*n
            for i in range(n):
                # if i was visited, potential cycles were already detected and updated
                if visited[i] == False:
                    seen = {}
                    while visited[i] == False:
                        visited[i] = True
                        # store current length for later computation of the cycle size, eg. 1,2,3,4,5,3... so size = 3
                        seen[i] = len(seen)
                        next_person = favorite[i]
                        # detect a cycle and update the size
                        if next_person in seen:
                            max_size = max(max_size, len(seen)-seen[next_person])
                            break
                        i = next_person
            return max_size
        def calculate_indegree(favorite):
            indegree = Counter(favorite)
            rank = defaultdict(lambda: 1)
            # store those people that are not pre-conditions of others
            free_people = list(set(range(n))-set(favorite))
            for person in free_people:
                next_person = favorite[person]
                # either take the original stored value, or connect to 'person' on one side
                rank[next_person] = max(rank[next_person], rank[person]+1)
                indegree[next_person] -= 1
                # now becomes new free person
                if indegree[next_person] == 0:
                    free_people.append(next_person)
            return rank
        largest_cycle = find_largest_cycle(favorite)
        self_contained_segments = 0
        indegree = calculate_indegree(favorite)
        for i in range(n):
            # only look to the right, to avoid double-counting
            next_person = favorite[i]
            if i < next_person and i == favorite[next_person]:
                self_contained_segments += indegree[i]+indegree[next_person]    # ..., i, favorite[i], ..., connect between ends
        return max(largest_cycle, self_contained_segments)

44400