發佈： 2025/09/29

2127. Maximum Employees to Be Invited to a Meeting - 從0開始思考

https://leetcode.com/problems/maximum-employees-to-be-invited-to-a-meeting/description/

題目理解

題目描述的是：公司要在一張圓桌召開會議，總共有 n 位員工，但這群人很難搞，每位員工都有自己最喜歡的同事，如果不能坐在這個同事旁邊，他就會拒絕出席

我們要計算：最多能邀請多少人參加會議

第一步: 最小情境分析

先用小案例理解規則：

1 個人
不可能參加（因為他沒有喜歡的人）
2 個人
- A 喜歡 B，但 B 不喜歡 A → 沒人參加
- A 喜歡 B，B 喜歡 A → 兩人都參加
3 個人
- A → B → C → 無人參加（C 沒有回饋）
- A → B ⇄ C → 三人都參加。
- A ⇄ B → C → A、B 參加，C 不參加
- A → B → C → A（成環）→ 三人都參加

第二步: 題目限制與圖的性質

題目條件給出：

n == favorite.length → 每個人都有且僅有一個喜歡的人

代表每個節點 outdegree = 1，圖由「鏈 (chain) + 環 (cycle)」組

favorite[i] != i → 沒有人是自戀

單一自環不存在

一個節點不可能同時指向兩人，因此:

環與環之間不相連
支鏈必定流向一個環

第三步: 哪些結構能組成圓桌？

由於規則限制，能參加的人必須形成「閉環」:

一般情況：只有環內的人能參加。任何支鏈上的人因為沒有回饋，無法坐下
例外情況：如果環長度 = 2（雙向喜歡），則兩條支鏈分別接在這兩個人身上，仍能一起坐下

因此，答案可能來自兩種情況：

單一環的大小
所有雙人環 + 對應支鏈的總和

第四步: 計算方法

刪掉支鏈，保留環

找 indegree = 0 的節點，從末端一路往內走，記錄支鏈長度

處理環

遍歷剩餘節點（未訪問過的就是環成員）
若環長度 > 2 → 記錄最大值
若環長度 = 2 → 加上兩個支鏈長度 + 2

最終答案
取下列兩者的最大值：

單一最大環
所有雙人環與支鏈組合的總和

實作

算出所有支鏈長度後排除支鏈的節點

找出支鏈末端: 必定是沒被指向的節點

vector<int> indegree(n, 0);
for (const int f : favorite) {
    indegree[f] += 1;
}

從末端開始向內計算直到遇到環，同時
1. 記錄被指向節點相連的鏈長(兩節點環的時候需要)
2. 將支鏈的節點標記為visited，環上的節點因為刪除支鏈之後還會有一個indegree因此不會被訪問到

queue<int> q;
vector<bool> visited(n, false);
for (int i = 0; i < n; i += 1 ) {
    if (indegree[i] == 0) {
        q.push(i);
    }
}

while (!q.empty()) {
    int cur = q.front();
    q.pop();
    visited[cur] = true;

    int next = favorite[cur];
    chain[next] = max(chain[next], chain[cur] + 1);
    if (--indegree[next] == 0) {
        q.push(next);
    }
}

計算剩餘的環長度並計算答案

任意未被訪問過的節點都是環的一員
沿著環traverse一周並且排除
1. 環節點 > 2，紀錄最大的環
2. 環節點 == 2，連著支鏈的長度一起計算到可能的最大可能性中

int maxCycle = 0;
int total = 0;
for (int i = 0; i < n; i += 1) {
    if (!visited[i]) {
        int cur = i;
        int cycleLength = 0;
        while (!visited[cur]) {
            visited[cur] = true;
            cur = favorite[cur];
            cycleLength += 1;
        }

        if (cycleLength == 2) {
            total += chain[i] + chain[favorite[i]] + 2;
        } else {
            maxCycle = max(maxCycle, cycleLength);
        }
    }
}

答案

最終答案會是最大的環，或是任意兩節點環+支鏈組合的總和其中比較大的那個

return max(maxCycle, total);

Solution

class Solution {
public:
    int maximumInvitations(vector<int>& favorite) {
        const int n = favorite.size();
        vector<int> indegree(n, 0);
        vector<int> chain(n, 0);
        vector<bool> visited(n, false);
        queue<int> q;

        for (const int f : favorite) {
            indegree[f] += 1;
        }

        for (int i = 0; i < n; i += 1 ) {
            if (indegree[i] == 0) {
                q.push(i);
            }
        }

        while (!q.empty()) {
            int cur = q.front();
            q.pop();
            visited[cur] = true;

            int next = favorite[cur];
            chain[next] = chain[cur] + 1;
            if (--indegree[next] == 0) {
                q.push(next);
            }
        }

        int maxCycle = 0;
        int total = 0;
        for (int i = 0; i < n; i += 1) {
            if (!visited[i]) {
                int cur = i;
                int cycleLength = 0;
                while (!visited[cur]) {
                    visited[cur] = true;
                    cur = favorite[cur];
                    cycleLength += 1;
                }

                if (cycleLength == 2) {
                    total += chain[i] + chain[favorite[i]] + 2;
                } else {
                    maxCycle = max(maxCycle, cycleLength);
                }
            }
        }

        return max(maxCycle, total);
    }
};