如何将树的父节点数组转邻接表？树祖先判定问题求助

针对你的代码，只需在遍历父节点数组时完成两个核心操作：将子节点添加到对应父节点的邻接表中，同时找到正确的根节点（原代码固定start=1存在逻辑错误，根节点是父节点为0的节点）。

具体修改步骤 #

1. 填充邻接表并定位根节点：在你标注的注释位置，插入以下代码：

   int p = anchestors[i];
   if (p != 0) {
       g[p].push_back(i);
   } else {
       start = i; // 记录父节点为0的根节点
   }
   

   逻辑说明：

   • 对每个节点i，获取其直接父节点p
   • 若p≠0，说明i是p的子节点，将i加入p的邻接表g[p]
   • 若p=0，说明i是根节点，将其赋值给start变量

2. 修正DFS起始参数：原代码中dfs(start,1)的第二个参数错误，根节点没有父节点，应改为dfs(start, 0)（因节点编号从1开始，0可表示无效父节点），避免DFS遍历根节点子树时出现判断错误。

修改后的完整核心代码片段 #

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin>>n;
    time_in.resize(n+1);
    time_out.resize(n+1);
    g.resize(n+1);
    vector<int> anchestors(n+1);
    int start = -1; // 初始化根节点变量
    for(int i=1; i<=n; ++i){
            cin>>anchestors[i];
            int p = anchestors[i];
            if (p != 0) {
                g[p].push_back(i);
            } else {
                start = i;
            }
    }

    dfs(start, 0); // 根节点父节点设为0，避免与有效节点混淆


    int q,u,v;
    cin>>q;
    while(q--){
        cin>>u>>v;
        cout<<isAnchestor(u,v)<<'\n';
    }
    return 0;
}

额外说明 #

• 邻接表g是二维vector，g[p]存储p的所有直接子节点，确保DFS能正确遍历整个树的结构。
• 根节点的父节点必须设为无效值（如0），否则DFS中to!=parent的判断会错误过滤根节点的子节点。

内容的提问来源于stack exchange，提问作者Isa