看看浙大學長（排名前20）的答案，好好學習
附上一個鏈接表示respect！
力扣原題答案
我的理解：
每個聯通分量有且僅有一環
環中若只有2node，則需要反向找出最長的樹枝（兩邊都找）
環中若大于2node，由于樹枝節點不可進環，樹枝節點不可成環，所以最多的人數就是環中人數
代碼思路：
代碼：
class Solution:
def maximumInvitations(self, g: List[int]) -> int:
# favorite就是內向基環森林g
n = len(g)
rg = [[] for _ in range(n)] # g的反圖
deg = [0] * n # g上每個點的入度
for v, w in enumerate(g):
# 反圖就是w指向v
rg[w].append(v)
deg[w] += 1
#print(deg)
#print(rg)
# 拓撲排序，剪掉g上的樹枝
# deque是雙向佇列, 找出入度為0的
q = deque(i for i, d in enumerate(deg) if d == 0)
#print(q)
# 遞回找樹枝
while q:
# v是樹枝末梢
v = q.popleft()
# 樹枝的上一個
w = g[v]
# 剪掉樹枝v
deg[w] -= 1
# 判斷剪掉v后w是否變成了樹枝末梢
# 這時候deg為0的都變成了樹枝
if deg[w] == 0:
# 右邊加
q.append(w)
# 通過反圖rg尋找樹枝上最深的鏈
def rdfs(v: int) -> int:
max_depth = 1
# v的反圖中
for w in rg[v]:
# 若入度為0，則是樹枝節點
if deg[w] == 0:
max_depth = max(max_depth, rdfs(w) + 1)
return max_depth
# 找出環元素>2的最大環元素個數
# 找出換元素=2的最長樹枝深度(包括基環那兩個)
max_ring_size, sum_chain_size =0, 0
for i, d in enumerate(deg):
# 不管樹枝
if d <= 0:
continue
# 遍歷基環上的點
deg[i] = -1
ring_size = 1
v = g[i]
while v != i:
deg[v] = -1 #將基環上的點的入度標記為-1,避免重復訪問
ring_size += 1
v = g[v]
# 若基環大小為2
if ring_size == 2:
# 累計兩條最長鏈的長度
sum_chain_size += rdfs(i) + rdfs(g[i])
else:
# 取所有基環的最大值
max_ring_size = max(max_ring_size, ring_size)
return max(max_ring_size, sum_chain_size)
基環為2之所以可以累加的解釋
總結：
1.這種誰喜歡誰模型可是內向基環圖森林
2.基環大于2，則不可插入，且樹枝不可組合，所以此時最大人數為基環（基環構成一個圈）
3.基環等于2，要計算兩邊各自最長鏈的和，且所有基環等于2的可以拼接起來
4.用rg、deg和enumerate記錄反圖（找最長鏈）和度數
5.用雙向佇列deque+拓撲排序（滿足邊的先后關系）找到所有樹枝
6.dfs找反向的最長鏈
7.遍歷deg，找出環中的點，分>2和==2兩種情況
8.兩者取max
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/402669.html
標籤：其他
上一篇：新年程式員福利（多圖）
下一篇：1135 求矩形個數（寧波OJ）