問題：
給定 N 個節點和 M 個邊的圖，邊的索引從 1 -> M。保證在任意 2 個節點之間存在路徑。
您需要為 M 條邊分配權重。權重在 [1...M] 范圍內，每個數字只能出現一次。
簡而言之，答案應該是 [1...M] 的排列陣列，其中 arr[i] = x 表示 edge[i] 具有 x 的權重。
給定一個由 n-1 條邊組成的集合 R。R 保證是圖的生成樹。
找到一種分配權重的方法，使 R 是圖形的最小生成樹，如果有多個答案，則列印具有最小詞典順序的答案。
限制：
N, M <= 10^6
例子：
邊緣：
3 4
1 2
2 3
1 3
1 4
R = [2, 4, 5]
Answer: 3 4 5 1 2
說明：
如果像上圖那樣為圖形分配權重，則 MST 將是集合 R，并且它具有最小的字典序。
我對 O(N^2) 的看法：
由于它要求最小字典順序，我遍歷邊串列，按遞增順序分配權重。最初，w = 1。可能有 3 種情況：
- 如果 edge[i] 在 R 中，分配 weight[i] = w，將 w 增加 1
- 如果 edge[i] 不在 R 中：說 edge[i] 連接節點 u 和 v。為 R 中從 u 到 v 的路徑中的每條邊分配權重并增加 w（如果該邊尚未分配）。然后為edge[i]分配權重并增加w
- 如果指定了 edge[i]，則跳過它
有什么方法可以改進我的解決方案，使其可以在 O(N.logN) 或更少的時間內作業？
uj5u.com熱心網友回復：
是的，有一個 O(m log m) 時間演算法。
該基本周期的非樹邊緣的?是由?和在端點之間的樹的路徑?。鑒于權重，生成樹最小當且僅當，為每個非樹邊e，在基本周期最重的邊緣?是?本身。
字典目標適用于貪婪演算法，我們找到邊 1 的最低有效分配，然后是邊 2 給定邊 1，然后邊 3 給定前邊等。這是核心思想：如果下一個未分配的邊是非樹邊，在其基本回圈中將下一個數字分配給未分配的樹邊；然后分配下一個數字。
在該示例中，邊 3-4 首先，邊 1-3 和 1-4 完成其基本回圈。因此我們分配 1-3 → ??1 和 1-4 → 2，然后 3-4 → 3。接下來是 1-2，樹邊，所以 1-2 → 4。最后， 2-3 → ??5 (1-2和 1-3 已經分配）。
為了有效地實作這一點，我們需要兩個要素：一種列舉基本回圈中未分配邊的方法，以及一種分配數字的方法。我對前者的建議是存盤指定邊收縮的生成樹。我們不需要任何花哨的東西；首先在某處生根生成樹并運行深度優先搜索以記錄父指標和深度。e的基本回圈將由到e的端點的最小公共祖先的路徑給出. 為了進行收縮，我們添加了一個布爾欄位來指示父邊是否收縮，然后使用來自不相交集森林的路徑壓縮技巧。作業將是 O(m log m) 最壞情況，但 O(m) 平均情況。我認為很有可能可以在這里插入離線最不常見的祖先演算法，以將最壞的情況降低到 O(m)。
至于數字分配，我們可以在線性時間內處理。對于每條邊，記錄導致它被分配的邊的索引。最后，根據該索引進行穩定的桶排序，通過將樹邊放在非樹之前來打破關系。這可以在 O(m) 時間內完成。
轉載請註明出處，本文鏈接：https://www.uj5u.com/caozuo/400692.html
上一篇：河內問題的迭代法如何求解