Структура данных, дерево, n-арное дерево, DFS - PullRequest
Новая
       84

Структура данных, дерево, n-арное дерево, DFS

0 голосов
/ 15 мая 2018

Я решаю простой вопрос на основе n-арного дерева. Вопрос прост, найти общее количество рукопожатий между солдатами, где каждый узел дерева представляет солдат. Только узлы предков могут рукопожатие.

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

Это 2552 год, Люди только что выиграли войну против очень могущественной инопланетной расы, которая вторглась в нашу солнечную систему. Человеческая армия находится в режиме празднования!

В армии n солдат. Солдаты чисел от 1 до n. Армия имеет иерархию превосходства. У каждого солдата есть один непосредственный начальник. Начальник начальника солдата также является начальником этого солдата. Так, у солдата может быть один или несколько начальников, но только один непосредственный начальник.

Каждый солдат должен поздравить всех остальных солдат. Для пары солдат, если один из них превосходит другого, они пожмут друг другу руки. В противном случае они будут бить кулаками.

Вам дан список непосредственных начальников всех солдат. Ваша задача - сказать, сколько будет рукопожатий и ударов кулаком.

Моя проблема в том, что я применил концепцию N-арного дерева, используя map, где int - ключевой элемент, хранящий родительский элемент, а vector of int - его дочерний элемент, и применил DFS, но после 2-й итерации мои значения изменились, например: 

     0                                             0
     |                                             |
     3                                             3
   /   \                                         /   \
  2     4                                       2      0    
 /                         changes to          /        
1                                             1

sample input:
1                                             //  ( test case)
4                                             //  ( number of nodes)
2 3 0 3                                       //  ( parent of node )

и из-за этого мой код переходит в цикл (от 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;
}

Я хотел знать, почему это происходит и где моя вина. В чем проблема в этом подходе? Я знаю, что есть еще много подходов, но почему это терпит неудачу?

...