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

# Approach


# We want to first find the maximum "chain" of elements ENDING AT i
# We can find this by linearizing and using topological sort.
                
        # NOTE: we know that by the end of topological sort, any unvisited vertices are part of a cycle, so we can then process those cycles separately
        # for person in range(n):
            # if not visited:
                # process the current cycle

# There are two 'classes' of solutions:
# Combined chains and mutuals - we can always add all of these up because mutuals sit next to each other and free up space on their sides
# OR the longest cycle in the graph

from collections import deque

class Solution:
    def _linearize(self, favorite: List[int], n: int):
        # tracks the number of people who have named this person as a favorite
        indegree = {}
        for fav in favorite:
            indegree[fav] = indegree.get(fav, 0) + 1
        # build our queue for topological sort
        # add sources i.e no fans to the deque
        queue = deque()
        for person in range(n):
            if not indegree.get(person):
                queue.append(person)
        # process graph
        # max chain length ending at (and not including) this person
        chainLen = [0 for _ in range(n)]
        processed = [False for _ in range(n)]
        while queue:
            curr = queue.popleft()
            processed[curr] = True
            fav = favorite[curr]
            # update fav
            chainLen[fav] = max(chainLen[fav], chainLen[curr] + 1)
            indegree[fav] -= 1
            # eval fav
            if indegree[fav] == 0:
                queue.append(fav)
        print(chainLen, processed)
        return chainLen, processed

    def maximumInvitations(self, favorite: List[int]) -> int:
        n = len(favorite)
        chainLen, processed = self._linearize(favorite, n)

        # There are two 'classes' of solutions:
        # Combined chains and mutuals - we can always add all of these up because mutuals sit next to each other and free up space on their sides
        # OR the longest cycle in the graph
        combinedChains = 0
        longestCycle = float('-inf')

        # process all people in cycles (i.e any vertex not processed during linearization)
        for person in range(n):
            # we are in a cycle
            if not processed[person]: 
                # find the cycle path
                curr, length = person, 0
                while not processed[curr]:
                    processed[curr] = True # mark processed
                    curr = favorite[curr] # move to next fave
                    length += 1
                # found end of cycle, update solution
                if length == 2:
                    # mutual favorites
                    combinedChains += chainLen[person] + chainLen[favorite[curr]] + 2
                else:
                    # cycle > 2
                    longestCycle = max(longestCycle, length)
        return max(combinedChains, longestCycle)
























###### 
# initial thoughts

    # circular table - everyone has two neighbors, left and right
    # favorite person is not themselves
    
    # how do i represent the circular nature of any given solution?
        # at any point in time, i probably need to be able to find the available seats in some way
    
    # favorite: [2, 2, 1, 2]
    # 4 employees

    # i know 2 is the most popular

    # fans who want to sit next to this person
    # 2: []

    # idea: anyone with >= 2 fans should ideally be siting next to those fans
    # HOWEVER, they will only come if they can sit next to their favorite
        # one seat is reserved for their favorite
    
    # if no one is chosen, can they attend the meeting
        # surprisingly, yes afaict - because we can linearize and so the people on the edges don't need to be interested in one another
    
    # does this reduce to the longest dag in this graph?

    # build a directed graph:

    # we already have the favorite edges
    # 0: 2
    # 1: 2
    # 2: 1 
    # 3: 2

    # fans edges - these are candidates once the favorite requirement has been fulfilled
    # 2: 0, 1, 3 -> reduce this to 1, 0, 3
    # 0... etc, missing


    # how do we determine where to start? 
    # start with people with the most fans to maximize
    
    # NOTE: if there are no sources (in degree = 0), everyone has been chosen at least once i.e by pigeonhole principle everyone can come

    # to traverse, we need to follow favorite edges
    # choose: 2 | {2 -> 1}
        # -> 1 | {2 -> 1} # done, since 1 does not want anyone else. go back to 2 as having an empty spot
        # 2 -> 3 | 
        #  -> 1 | {3 -> 2 -> 1}
        # 1 -> 2 # we've already seen two, and 1 has no fans besides 2, so we're done

            # if the previous is the favorite, we cannot traverse the favorite edge, BUT we can add someone else
                # check fan edges and if not in current path, queue these to evaluate
                        # dp - pick the max that comes back from here
            # if the favorite has already been added, we're done; cannot go further
            # otherwise we can add the favorite, so choose the favorite edge next
    
    # test algo on example 3
    # favorite = [3, 0, 1, 4, 1]
    # fans:
        # {
        #     0: 1,
        #     1: 2, 4,
        #     2: None (source),
        #     3: 0,
        #     4: 3
        #     }

    # find the longest cycle in the graph..??
                
38300