0

我正在解决一个基于 n 叉树的简单问题。问题很简单，找出士兵之间握手的总数，其中树的每个节点代表士兵。只有祖先节点可以握手。

https://www.hackerearth.com/practice/data-structures/trees/binary-and-nary-trees/practice-problems/algorithm/comrades-ii-6/

这是 2552 年，人类刚刚赢得了一场与入侵我们太阳系的非常强大的外星种族的战争。人类军队进入庆祝模式！

军队有n个士兵。士兵是从 1 到 n 的数字。军队有优势等级。每个士兵都有一个直属上司。一个士兵的上级的上级也是那个士兵的上级。因此，一名士兵可能有一个或多个上级，但只有一个直接上级。

每个士兵都必须祝贺其他每个士兵。对于一对士兵来说，如果其中一个是另一个的上级，他们会握手。否则，他们会碰拳头。

您将获得所有士兵的直接上级名单。你的工作是告诉你会有多少次握手和拳头碰撞。

我的问题是我使用 map 应用了 N-ary 树概念，其中int关键元素存储父元素并vector of int作为其子元素，并应用了 DFS，但在第二次迭代后我的值发生了变化，例如：

     0 0
     | |
     3 3
   / \ / \
  2 4 2 0    
 / 更改为 /        
1 1

样本输入：
1 //（测试用例）
4 //（节点数）
2 3 0 3 //（节点的父节点）

因此，我的代码进入循环（0 到 3，然后 3 到 0），因此出现分段错误。我完全搞砸了，尝试了一切，但什么也没发生。

这是我的代码：

#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
using namespace std;
static long long int count1 = 0;

vector<int>::iterator itr;
map<int,vector<int> >tree;

void dfs(map<int,vector<int> > &tree, int node, int height){
    if(tree.find(node) == tree.end() ){
        return ;
    }
    if(tree[node].empty()){
        return ;
    }
    for(itr = tree.at(node).begin(); itr != tree.at(node).end(); itr++){    
        cout<<"node : "<<node <<"   child : "<<*itr<<endl;
        count1 += height;
        dfs(tree,*itr,height+1);
    }
}
int main(){
    int T,N,X;
    cin>>T;
    for(int i=0;i<T;i++){
        cin>>N;
        for(int j=1;j<=N;j++){
            cin>>X;
            tree[X].push_back(j);
        }

        dfs(tree,tree[0].front(),1);
        cout<<count1<<endl;
        count1 -= count1;
        tree.clear();
    }
    return 0;
}

我想知道为什么会这样，我的错在哪里。这种方法有什么问题？我知道还有更多方法，但为什么会失败？

4

0 回答 0