會有很多查詢。每個查詢 (A,B,K) 都要求您檢查是否可以在從 A 到 B 的路徑中找到一個節點 (value=K)。解決方案預計不超過 O(n qlogq), n,q : node計數，查詢計數。
我心里有個解決辦法。我把它貼下來。我想知道其他方法是什么。
我的方法：
查找 A 和 B 之間的 LCA（最低共同祖先）。檢查 K 是否是 A 或 B 的祖先。如果是=>檢查 LCA 是否是 K 的祖先。如果是，則輸出 yes。要確定一個頂點是否是另一個頂點的祖先，我們可以檢查一個頂點是否存在于另一個頂點的子樹中。（如果我們在 dfs 中預處理節點的進出訪問順序，這可以在 O(1) 中完成。https: //www.geeksforgeeks.org/printing-pre-and-post-visited-times-in-dfs-of- a-圖/ )
但是如果所有查詢都具有相同的 K 值，則復雜性會增加。我們需要檢查所有滿足 A 或 B 進出時間的 K。因此，為了優化，我們可以將所有 K 分別與 DFS 的進出時間排序。
有什么想法嗎？
uj5u.com熱心網友回復：
在 U 和 V 之間的路徑中存在 R 的情況如下：
- R 是 U 和 V 的最低共同祖先。
- R 在 LCA(U,V) 和 U 之間的路徑上。
- R 在 LCA(U,V) 和 V 之間的路徑上。
// Function that return true if R
// exists on the path between U
// and V in the given tree
bool isPresent(int U, int V, int R)
{
// Calculating LCA between U and V
int LCA = lowestCommonAncestor(U, V);
// Calculating LCA between U and R
int LCA_1 = lowestCommonAncestor(U, R);
// Calculating LCA between U and V
int LCA_2 = lowestCommonAncestor(V, R);
if (LCA == R || (LCA_1 == LCA && LCA_2 == R) ||
(LCA_2 == LCA && LCA_1 == R)) {
return true;
}
return false;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/caozuo/420160.html
標籤：