<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:
        return max(self.get_max_cycle_length(favorite), self.get_max_chain_without_cycle_length(favorite))
    def get_max_cycle_length(self, favorite: List[int]) -> int:
        person_cnt = len(favorite)
        max_cycle_length = 0

        seen = set()

        # for each person
        for i in range(person_cnt):
            # i - person i

            # if person not part of any chain (chain with cycle)
            if i in seen:
                continue
            
            # begin of chain (chain with cycle)
            begin_person = i

            # visited nodes inside of chain (chain with cycle)
            cur_visited = set()

            # cur_person
            cur_person = i

            # try to build chain with cycle
            while cur_person not in seen:
                seen.add(cur_person)
                cur_visited.add(cur_person)
                cur_person = favorite[cur_person]
            
            # if cycle exists
            if cur_person in cur_visited:
                # length of chain with cycle
                visited_person_cnt = len(cur_visited)

                # try to find length of cycle
                while begin_person != cur_person:
                    visited_person_cnt -= 1
                    begin_person = favorite[begin_person]
            
                max_cycle_length = max(max_cycle_length, visited_person_cnt)
        
        return max_cycle_length
    
    def get_max_chain_without_cycle_length(self, favorite: List[int]) -> int:
        person_cnt = len(favorite)
        max_chain_len = 0

        # find mutal-favorite (a <-> b) pairs
        pairs = []
        visited = set()

        for i in range(person_cnt):
            if i not in visited and favorite[favorite[i]] == i:
                pairs.append((i, favorite[i]))
                visited.add(i)
                visited.add(favorite[i])

        # build deps list, list that consits from deps from i (a -> b and c -> b, we shoul build such list [a,c] for b)
        deps = collections.defaultdict(list)
        for i in range(person_cnt):
            deps[favorite[i]].append(i)

        for src, dst in pairs:
            # max chain length to src
            max_dist_to_src = 0
            
            q = collections.deque()
            for dep in deps[src]:
                if dep != dst: q.append((dep, 1)) # dependent node and dist to dependent node
            
            while q:
                cur_dependency, dist = q.popleft()
                max_dist_to_src = max(max_dist_to_src, dist)
                for next_dep in deps[cur_dependency]:
                    q.append((next_dep, dist + 1))
            
            max_dist_to_dst = 0
            q = collections.deque()
            for dep in deps[dst]:
                if dep != src: q.append((dep, 1))
            
            while q:
                cur_dependency, dist = q.popleft()
                max_dist_to_dst = max(max_dist_to_dst, dist)
                for next_dep in deps[cur_dependency]:
                    q.append((next_dep, dist + 1)) 

            max_chain_len += 2 + max_dist_to_src + max_dist_to_dst

        return max_chain_len


    # def maximumInvitations(self, favorite: List[int]) -> int:
        
    #     res = set()
    #     chain = 0
    #     arm = {}
    #     cache = set()
    #     for person in range(len(favorite)):
    #         if person in cache:
    #             continue
    #         cache_chain = set()
    #         count = 0
    #         head = person
    #         tail = -1
    #         while person not in cache_chain:
    #             second_tail = tail
    #             tail = person
    #             cache_chain.add(person) 
    #             count += 1
    #             person = favorite[person]
    #         if favorite[tail] == second_tail:
    #             # print("one way",cache_chain)
    #             if not (second_tail, tail) in arm:
    #                 arm[(second_tail,tail)] = len(cache_chain)
    #             else:
    #                 arm[(second_tail, tail)] = max(arm[(second_tail, tail)], len(cache_chain))
    #             cache.add(tail)
    #             cache.add(second_tail)
    #         elif head == favorite[tail]:
    #             print("chain", cache_chain)
    #             chain = max(chain, len(cache_chain))
    #             cache = cache.union(cache_chain)


        
    #     arm_length = 0
    #     cache_arm = set()
    #     for i,j in arm:
    #         if (i,j) in cache_arm:
    #             continue
    #         if (j,i) in arm:
    #             arm_length += arm[(i,j)] + arm[(j,i)] - 2
    #             cache_arm.add((j,i))
    #         else:
    #             arm_length + arm_length, arm[(i,j)]
    #     return max(chain, arm_length)
45300