HardRating 3018

1719. Number Of Ways To Reconstruct A Tree

arrayhash-tabletreegraphsimulation

解題說明

Number Of Ways To Reconstruct A Tree

題目描述：給定一組配對 pairs，其中 pairs[i] = [x, y] 表示在一棵有根樹中 x 是 y 的祖先或 y 是 x 的祖先。判斷能構成多少棵合法的有根樹：0（不可能）、1（唯一）或 2（多於一種）。

解題思路：對每個節點計算其度數（與之配對的節點數）。度數最大的節點必為根，其度數等於 n-1。將節點按度數降序排列後逐一處理。對每個節點 v，找到在排序中它之前且度數最小的鄰居 u 作為其父節點。檢查 u 的鄰居是否為 v 的鄰居的超集（祖先性質）。若任何檢查失敗回傳 0。若存在度數相同的父子對（可互換），回傳 2，否則回傳 1。

C++ 解法

複雜度分析

時間複雜度：O(n × m) — 其中 n 為節點數，m 為每個節點的平均鄰居數。最壞情況下為 O(n^2)，但在稀疏圖中效率更好。

空間複雜度：O(n + |pairs|) — 鄰接表儲存所有配對關係。

虛擬碼

1. Build adjacency sets from pairs
2. Sort nodes by degree descending
3. If root (highest degree) does not have degree n-1, return 0
4. For each node v (in sorted order):
   a. Find parent = neighbor with smallest degree >= deg(v)
   b. If no parent found and v is not root, return 0
   c. Check all neighbors of v (except parent) are also neighbors of parent
   d. If check fails, return 0
   e. If parent has same degree as v, mark multipleWays = true
5. Return 2 if multipleWays, else 1

其他解法

Prufer 序列枚舉：嘗試所有可能的樹結構並驗證。理論上完備但 n 較大時不可行（樹的數量為 n^(n-2)）。

增量建樹法：從根開始，按度數大小依次掛載子節點，每步驗證配對約束。邏輯等價但以建樹視角思考更直觀。

延伸思考

若配對關係允許包含非祖先-後代的節點對，如何驗證？
若要實際輸出一棵合法的樹結構，如何在判斷的同時建樹？
若要求計算所有合法樹的確切數量（不只是 0/1/2），問題的複雜度如何？

Number Of Ways To Reconstruct A Tree — CaffeCode