🔗 🔴 2127. Maximum Employees to Be Invited to a Meeting

題意

有 nn 名員工要參加會議，會議桌是 圓形 的，且可以坐下任意數目的人。

每個員工都有 一位 喜歡的員工，且喜歡的員工不會是自己，只有旁邊坐在喜歡員工的旁邊時，該員工才會參加會議。

給定一個整數陣列 favorite\textit{favorite} ，其中 favorite[i]\textit{favorite}[i] 表示第 ii 位員工喜歡的員工，請問最多有幾位員工可以參加會議？

約束條件

  • 2≤n≤1052 \leq n \leq 10^5
  • 0≤favorite[i]≤n−10 \leq favorite[i] \leq n - 1
  • favorite[i]≠ifavorite[i] \neq i

思路：基環樹(pseudotree)與基環樹森林(pseudoforest)

首先可以將每個員工視為圖上的一個點，並且向其喜歡的員工連有向邊，即從 ii 向 favorite[i]favorite[i] 連一條有向邊，則可以得到一張有向圖。注意到題目中每個員工都有且僅有一位喜歡的員工，且喜歡的員工不會是自己，因此可以得知每個點的 out-degree 均為 11。

根據這個性質，可以得出圖的形狀：圖中存在若干個連通分量(connected component)，且每個連通分量都由一個環以及指向環的樹枝組成，證明如下：

  • 設此連通分量的大小為 kk，即存在 kk 個點，由於每個點的 out-degree\textit{out-degree} 均為 11，因此這個分量有且僅有 kk 條邊。
  • 若其不包含環，則最多只能有 k−1k-1 條邊，否則與每個點的 out-degree\textit{out-degree} 均為 11 矛盾，或是添加任何一條邊都會導致環的出現。
  • 又由於每個點的 out-degree\textit{out-degree} 均為 11，因此若某個連通分量中不包含環，則該連通分量中必定存在一個點的 out-degree\textit{out-degree} 為 00，這也與每個點的 out-degree\textit{out-degree} 均為 11 矛盾。

對於圖中的每個連通分量，可以將其環上的每個點視作樹的根節點，而這樣的連通分量被稱為 基環樹(pseudotree)。且圖中會有多個這樣的連通分量，由基環樹組成的森林叫 基環樹森林(pseudoforest)。

  • 基環 指的是連通分量中的環，且基環樹中 有且僅有一個環 ，需要注意的是， 基環可能只包含兩個節點。下圖用紅色標記了基環。
  • 由於圖中任意節點有且只有一條出邊，因此邊的方向會指向環，因此這樣的圖被稱做 內向 基環樹森林。
  • 對應的情況是圖中任意節點有且只有一條入邊，這樣的圖會從環指向外側，因此被稱做 外向 基環樹森林。
內向基環樹森林 1 1 2 2 1->2 2->1 3 3 3->1 4 4 4->2 10 10 10->3 11 11 11->3 5 5 6 6 5->6 7 7 6->7 7->5 8 8 8->6 9 9 9->7
內向基環樹森林

在得到圖的形狀後，接下來考慮在這些連通分量中，分別可以選擇多少個員工參加會議：

  • 對於基環長度 >2>2 的情況，只能選擇基環上的所有員工，且只能以環的形狀選擇。故對於此種情況，最大員工數目即為最大的基環長度，記作 maxRing\textit{maxRing}。
  • 對於基環長度 =2=2 的情況，其基環可以與兩側最長鏈相連，形成一個更長的鏈。且對於這種情況，可以將這些鏈繼續連接，故可以累加所有基環長度為 22 的基環樹的鏈長，記作 sumChain\textit{sumChain}。
長度為 2 的情況 1 1 2 2 1->2 2->1 4 4 4->2 10 10 3 3 10->3 3->1
長度為 2 的情況

最後考慮如何找到基環樹上的環以及鏈長：

  • 一種方法是從葉節點開始，不斷向根節點移動，直到遇到環為止，而內向基環樹的葉節點即為入度為 00 的節點。因此可以統計每個點的 in-degree\textit{in-degree} ，從入度為 00 的點開始對圖進行 拓樸排序(topological sort)，剩餘的點都是基環上的點，
  • 而找以某個點為根節點的鏈長，可以通過對其進行 DFS ，找到以該點為根節點的樹高。但由於我們給定的圖是從葉節點指向根節點，因此需要對圖進行 反向建圖 ，才能從根節點開始進行 DFS 找到樹高。

一些注意事項：

  • 由於我們要在基環樹上的根節點開始 DFS ，因此建反圖時不能包含環的部分。
  • 為了避免重複處理相同基環上的點，可以標記處理過的基環上的點。

複雜度分析

  • 時間複雜度：O(n)\mathcal{O}(n)
    • 在拓樸排序和反向建圖的過程中，每個點最多被處理一次。
    • 在找基環上的點的過程中，每個點也最多被處理一次。
  • 空間複雜度：O(n)\mathcal{O}(n)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
class Solution:
    def maximumInvitations(self, favorite: List[int]) -> int:
        n = len(favorite)
        ind = [0] * n
        for f in favorite:
            ind[f] += 1
        
        rg = [[] for _ in range(n)]
        q = deque(i for i, d in enumerate(ind) if d == 0)
        while q: # 拓樸排序
            u = q.popleft()
            v = favorite[u]
            rg[v].append(u) # 反向建圖
            ind[v] -= 1
            if ind[v] == 0:
                q.append(v)

        # 通過 reverse graph，找到最大樹高
        def rdfs(u: int) -> int:
            res = 1
            for v in rg[u]:
                res = max(res, rdfs(v) + 1)
            return res
        
        max_ring = sum_chain = 0
        for u, d in enumerate(ind): # 遍歷所有基環上的點
            if d == 0: # 入度為 0 代表非基環上的點或者已經訪問過，跳過
                continue

            # 找到基環上的所有點
            rings = [u]
            v = favorite[u]
            while v != u:
                rings.append(v)
                v = favorite[v]
            for v in rings:
                ind[v] = 0 # 將基環上的點的入度標記為 0，避免重複訪問
            
            # 若基環長度為 2，則可以選擇基環以及兩側的最長鏈，且其仍然可以展開為鏈，因此可以有多個長度為 2 的基環
            if len(rings) == 2: 
                sum_chain += rdfs(u) + rdfs(favorite[u])
            # 若基環長度大於 2，則只能選擇基環本身
            else:
                max_ring = max(max_ring, len(rings))

        return max(max_ring, sum_chain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
class Solution {
 public:
  int maximumInvitations(vector<int>& favorite) {
    int n = favorite.size();
    vector<int> ind(n);
    for (int f : favorite) ind[f]++;

    vector<vector<int>> rg(n);
    queue<int> q;
    for (int i = 0; i < n; ++i)
      if (ind[i] == 0) q.push(i);

    while (!q.empty()) {
      int u = q.front();
      q.pop();
      int v = favorite[u];
      rg[v].push_back(u);
      ind[v]--;
      if (ind[v] == 0) q.push(v);
    }

    auto rdfs = [&](auto&& rdfs, int u) -> int {
      int res = 1;
      for (int v : rg[u]) 
        res = max(res, rdfs(rdfs, v) + 1);
      return res;
    };

    int max_ring = 0, sum_chain = 0;
    for (int u = 0; u < n; ++u) {
      if (ind[u] == 0) continue;

      vector<int> rings = {u};
      int v = favorite[u];
      while (v != u) {
        rings.push_back(v);
        v = favorite[v];
      }
      for (int v : rings) ind[v] = 0;

      if (rings.size() == 2)
        sum_chain += rdfs(rdfs, u) + rdfs(rdfs, favorite[u]);
      else
        max_ring = max(max_ring, (int)rings.size());
    }
    return max(max_ring, sum_chain);
  }
};

類題

參考資料

寫在最後

PROMPT

In a beautiful anime style, a young girl stands in front of a backdrop of densely blooming cherry blossoms. She is wearing a white short-sleeved shirt paired with a light purple skirt and a purple ribbon, exuding a fresh and elegant aura. Her hair is a deep brown short cut, with bangs parted to reveal a delicate face. Her left hand is raised gently while her right hand holds a bouquet of pink flowers, posing naturally. The background is slightly blurred but filled with an abundance of cherry blossoms, enhancing the romantic and serene atmosphere. The contrast is intensified, making the colors more vibrant and the overall scene more striking, capturing a poetic and picturesque moment.