# 2127. Maximum Employees to Be Invited to a Meeting
from collections import defaultdict, deque
"""
a company is organising a meeting and has a list of 'n' employees, waiting to
be invited. they have arrange for a large circular table, capable of seating
any number of employees. the employees are numbered from 0 to 'n - 1'. each
employee has a favourite person and they will attend the meeting only if they
can sit next to their favourite person. the favourite person of an employee
is not themselves. given a 0 indexed integer array 'favorite' where
'favorite[i]' denotes the favourite person of the i'th employee, return the
maximum number of employees that can be invited.
"""
class Solution(object):
def maximumInvitations(self, favorite):
"""
:type favorite: List[int]
:rtype: int
"""
indegrees = defaultdict(list)
for idx, fav in enumerate(favorite):
indegrees[fav].append(idx)
def bfs(start, seen):
q, res = deque([(start, 0)]), 0
while q:
pos, dist = q.popleft()
for i in indegrees[pos]:
if i in seen:
continue
seen.add(i)
q.append((i, dist + 1))
res = max(res, dist + 1)
return res
n = len(favorite)
cycle_largest, cycle_sum = 0, 0
for i in range(n):
if favorite[i] != -1:
dist = {i: 0}
while favorite[i] != -1:
next = favorite[i]
favorite[i] = -1
if next in dist:
cycle_len = len(dist) - dist[next]
cycle_largest = max(cycle_largest, cycle_len)
if cycle_len == 2:
cycle_sum += 2 + bfs(next, {i, next}) + bfs(i, {i, next})
else:
i = next
dist[next] = len(dist)
return max(cycle_largest, cycle_sum)
if __name__ == "__main__":
obj = Solution()
print(obj.maximumInvitations(favorite=[2, 2, 1, 2]))
print(obj.maximumInvitations(favorite=[1, 2, 0]))
print(obj.maximumInvitations(favorite=[3, 0, 1, 4, 1]))
