2127. Maximum Employees to Be Invited to a Meeting

문제

A company is organizing a meeting and has a list of n employees, waiting to be invited. They have arranged 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 favorite person and they will attend the meeting only if they can sit next to their favorite person at the table. The favorite person of an employee is not themself.

Given a 0-indexed integer array favorite, where favorite[i] denotes the favorite person of the ith employee, return the maximum number of employees that can be invited to the meeting.

한 회사에서 회의를 조직하고 있으며, 초대될 n명의 직원 목록이 있습니다. 회사는 직원 수에 상관없이 앉을 수 있는 큰 원형 테이블을 준비했습니다.

직원들은 0번부터 n-1번까지 번호가 매겨져 있습니다. 각 직원은 좋아하는 사람이 있으며, 본인이 좋아하는 사람 옆에 앉을 수 있는 경우에만 회의에 참석합니다. 직원이 좋아하는 사람은 본인이 아닙니다.

0-인덱스 정수 배열 favorite가 주어지며, favorite[i]는 i번 직원이 좋아하는 사람을 나타냅니다. 회의에 초대할 수 있는 직원의 최대 수를 반환하세요.

---

예시

favorite = [2,2,1,2]

• 위와 같이 앉는것이 가장 많이 앉을수 있다.

---

제한

• $n == favorite.length$
• $2 <= n <= 10^5$
• $0 <= favorite[i] <= n - 1$
• $favorite[i] != i$

---

풀이

• 여기에서 정답은 둘 중 하나이다.

1. 가장 큰 사이클의 크기
2. 사이클이 2개인 그래프들에서의 최장 경로들의 합

• 이 두개를 구해서 비교 후 리턴한다.

class Solution:
    def maximumInvitations(self, favorite: List[int]) -> int:
        ## Find Largest cycle

        longest = 0

        visit = set()

        N = len(favorite)

        length_2_cycle = []

        for i in range(N):
            if i in visit:
                continue
        
            start = i
            cur = i
            cur_set = set()

            while cur not in visit:
                visit.add(cur)
                cur_set.add(cur)
                cur = favorite[cur]

            length = len(cur_set)

            while start != cur:
                length -= 1
                start = favorite[start]

            longest = max(longest, length)
            
            if length == 2:
                length_2_cycle.append([cur, favorite[cur]])

        
        inverted = defaultdict(list)

        for dst, src in enumerate(favorite):
            inverted[src].append(dst)

        def bfs(node: int, parent: int):
            q = deque([(node, 0)])

            size = 0

            while q:
                x = q.popleft()
                current, count = x

                if current == parent:
                    continue

                size = max(size, count)
                
                for to in inverted[current]:
                    q.append((to, count + 1))

            return size

        size = 0

        for n1, n2 in length_2_cycle:
            size += bfs(n1, n2) + bfs(n2, n1) + 2

        return max(longest, size)