<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:
        # x will only sit at the meeting if favorite[x] is seated next to them

        # tried complicated loop detection thing with fast and slow and prefix
        #   it was neat, and complicated, and also WRONG :(
        
        # example: 1 0 0 2 1 4 7 8 9 6
        #          0 1 2 3 4 5 6 7 8 9

        #  3 -> 2 -> 0 -> 1 <- 4 <- 5
        #             \<-/


        # suppose we chase a cycle ending with a loop of 2
        #       3 -> 2 -> 1 -> 0 -> 1**
        #
        #    if the loop is of length 2 then the prefix is ok, and the loop is fine, so all is good
        #
        #    if the loop is of length 3+ then we have a problem because we'd have p1 -> p2 -> ... pk -> A -> B -> C -> A**
        #
        #         C prefers A, but C isn't placed next to A because there's a prefix
        #
        #     so we have to either drop the prefix, taking the loop only
        #
        # when loop has size 2:
        #          A ->  B
        #           \   /
        #             <-
        #
        # if there's a prefix going to A and a prefix going to B then we can do pA1 .. pA_m A B pBn .. pB1

        # how do we do this in a sane amount of effort?
        #
        #
        # we can start with finding loops
        # then for each node in the loop we set loop_length = L
        # and for each node in the loop we use DFS on `prev` to fill in max_prefix

        # then answer is max loop length > 2
        # for a L=2 loop, 2 + sum of max prefix lengths

        n = len(favorite)

        prev = [[] for _ in range(n)]
        for i, f in enumerate(favorite):
            prev[f].append(i)

        loop_len = [0]*n
        max_prefix = [0]*n # max_prefix[h] is longest prefix that leads to loop node h (h == "head of loop")

        def set_max_prefix(h: int):
            """Sets the max prefix length of `h`. Also marks those prefix nodes as seen, loop_len[prefixNode] = -1"""
            L = loop_len[h]

            # all previous nodes (those favoring h) that are NOT in the loop
            q = deque(p for p in prev[h] if loop_len[p] == 0)
            while q:
                # there are nodes at the next distance: increase max prefix length
                max_prefix[h] += 1

                for _ in range(len(q)):
                    p = q.popleft()
                    loop_len[p] = -1 # mark as seen
                    q.extend(prev[p]) # prev chain is directed tree structure, no need to check a seen/visited flag


        for i in range(n):
            if loop_len[i]: continue

            # find the loop i leads to
            slow = favorite[i]
            fast = favorite[slow]
            while slow != fast:
                slow = favorite[slow]
                fast = favorite[favorite[fast]]

            # determine loop size
            L = 1
            slow = favorite[slow]
            while slow != fast:
                L += 1
                slow = favorite[slow]

            # set L for all nodes in the loop
            for _ in range(L):
                loop_len[slow] = L
                slow = favorite[slow]

            for _ in range(L):
                set_max_prefix(slow)
                slow = favorite[slow]

        # one alternative: take any one loop > 2
        most_oneloop = max((loop_len[i] for i in range(n) if loop_len[i] > 2), default=0)

        # print(f"{loop_len=}")
        # print(f"{max_prefix=}")

        # other alternative: for every dimer of the form D1, D2 we have
        #                   l1 > l2 > ... > D1 >< D2 < r1 < r2 < ... r_last
        # we can concatenate all such dimer pairs with prefixes
        # so for each dimer take the longest prefix of both sides

        most_dimers = 0
        for i in range(n):
            if loop_len[i] == 2:
                most_dimers += 2 + max_prefix[i] + max_prefix[favorite[i]]
        most_dimers //= 2 # overcounted by two b/c we hit each dimer twice

        return max(most_oneloop, most_dimers)
37400