https://leetcode.com/problems/maximum-employees-to-be-invited-to-a-meeting/description/
有 n
位員工,會議室有一張圓桌可坐任意數量的人
員工編號從 0
到 n-1
,給定一個長度 n
的陣列 favorite
分別代表每位員工希望自己旁邊一定要坐哪位員工,任意員工 i
之 favorite[i]
保證不為 i
自己
回傳最多可讓多少員工坐在圓桌前,滿足每位員工旁邊皆坐著自己的 favorite person
這題看似簡單,但還是需要非常細心的考慮
絕對沒有實際上看起來容易
我們以 example 1 為例:
favorite = [2,2,1,2]
如果我們把 favorite 關係看作有向邊,那麼這題就能變成在有向圖上的問題
對圖論足夠敏銳的人此刻應該要能發現,我們造出來的有向圖必定含有 cycle
怎麼說呢?因為我們有 個頂點,以及 條邊,所以圖中必定含有 cycle
例如上圖中 跟 形成長度為 的 cycle
那知道了這件事又能怎樣呢?
我們先換個例子來看:
我們會注意到,圖中最長的那個 cycle
會能讓最多人入座圓桌
那麼剩下的人呢?
我們再看回 example 1
長度最長的 cycle 就是
但 跟 也跟 相鄰,我們還能再挑人入圓桌
這是因為 3-cycle 以上才會形成封閉小圈圈,如果我們只是兩人互相喜歡 (lenCycle == 2
) 那麼還需要考慮其他指過來的頂點才行
考慮的方法其實也是想辦法抓最長的那條 chain 裡的成員進來
例如 ( 也行) 這條 chain 長度為 ,比我們只看 cycle 的長度還長
所以最終答案就是
根據題意,每位員工只會有一位不是自己本人的 favorite person ,換句話說就是有向圖上每點 out degree 為 且圖上無 loop
我們想要找 chain ,關鍵就在於還有哪些人指過來到 2-cycle 上的頂點嘛,也就是說我們是要看 in degree
先初始化 indeg
:
接著我們先看沒人喜歡的員工 (nodes[u].indeg == 0
) ,看看這些員工都喜歡誰
這個過程是未來需要找 chain 時,找出最長的那條 chain 用的
想法就是 2-cycle 上的頂點為終點的話,除起點外應該會有能一路從起點指過來的路徑,即為 chain
為了方便,我們初始化 nodes[u].dist == 1
(每個點都是長度為 的 chain),每次我們比較 u
跟其喜歡的 v
兩者的 chain 長度: max(nodes[v].dist, nodes[u].dist + 1)
其中 nodes[u].dist + 1
代表接上 u
後的長度,並且跟 v
當前最長的長度比,每次更新
更新 v
的原因是因為我們期望 2-cycle 上的頂點會當作 v
的角色
更新之後,別忘了要標示拜訪過的點,做法就是把這個入度扣掉 (--node[v].indeg
) ,表示 u
考慮過了,少掉一個射入 v
的頂點
如果 v
這般操作後也變成入度為 的點,就要把他加入拜訪
上述準備完後,我們就可以找最長的 cycle 了,並且跟最長 chain (2-cycle 上兩點的 chain 長度相加) 做比較,取最大值即為所求
如果是 cycle 上的點,那肯定是有 cycle 上的其他頂點射向他,上述操作過後,這些點的入度必不為 ,由此我們就能找出 cycle 了