⚡Flashcard Drill➔
NeetCode #647LC-2127HardAdvanced Graphs
← Back to All Problems

#647 · #2127 · Maximum Employees to Be Invited to a Meeting(参加会议的最多员工数)

📌 Problem Statement & Constraints

There are n employees, each with one favourite colleague given in favorite[i]. Seating is circular and each person must sit next to their favourite. Return the maximum number who can be seated. Constraints: 2 <= n <= 10^5, 0 <= favorite[i] < n, favorite[i] != i.

💡 Core Algorithmic Approaches

  1. The favourite relation is a functional graph: each node has exactly one outgoing edge, so every component has exactly one cycle.
  2. Case 1 -- cycle of length 2: the two people can sit next to each other, and each can additionally bring the longest chain pointing into them. Sum all such 2-cycles' chains.
  3. Case 2 -- longer cycle: only the cycle itself can be seated (chains cannot attach), so the answer is the longest cycle.
  4. Peel in-degree-0 nodes first to identify the cycle nodes and the chain depths.

💻 Benchmark Python3 Implementation

class Solution:
    def maximumInvitations(self, favorite: List[int]) -> int:
        from collections import deque
        n = len(favorite)
        indeg = [0] * n
        for f in favorite:
            indeg[f] += 1

        # peel nodes not on a cycle, tracking the longest chain depth into each
        depth = [1] * n
        q = deque(i for i in range(n) if indeg[i] == 0)
        while q:
            node = q.popleft()
            nxt = favorite[node]
            depth[nxt] = max(depth[nxt], depth[node] + 1)   # chain length
            indeg[nxt] -= 1
            if indeg[nxt] == 0:
                q.append(nxt)

        # remaining nodes (indeg > 0) are exactly the cycle nodes
        seen = [False] * n
        pairs_total = 0                    # sum over 2-cycles
        max_cycle = 0                      # the longest cycle
        for i in range(n):
            if indeg[i] > 0 and not seen[i]:
                cycle = []
                cur = i
                while not seen[cur]:
                    seen[cur] = True
                    cycle.append(cur)
                    cur = favorite[cur]
                if len(cycle) == 2:
                    # both can bring their longest chains
                    pairs_total += depth[cycle[0]] + depth[cycle[1]]
                else:
                    max_cycle = max(max_cycle, len(cycle))
        return max(pairs_total, max_cycle)

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n): the peeling and the cycle walk each visit every node once.
💾 Space Complexity
O(n) for the in-degree and depth arrays.

⚠️ Interview Pitfalls & Follow-ups

  • Summing all cycle lengths: only 2-cycles can absorb chains; longer cycles are taken alone.
  • Forgetting to peel the non-cycle nodes: the cycle detection would be ambiguous.
  • Using depth initialised to 0: a node alone has chain depth 1.
  • Taking the maximum of a single 2-cycle instead of the sum: all 2-cycles contribute additively.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔

🧩 Related Advanced Graphs Problems