1

私はこのコードを回すことに問題があります：

void dfs(int i = 1) {
  static int preorder = 0;
  d[i].first = ++preorder;
  d[i].second = 1;
  for (list<int>::iterator it = tree[i].begin(); it != tree[i].end(); ++it) {
    dfs(*it);
    d[i].second += d[*it].second;
  }
}

反復的なものに。ご覧のとおり、各ノードの事前注文番号とその子孫の数がわかります。メモリ制限のためにそれをしなければなりません（データサイズは最大10 ^ 6です）。

前もって感謝します。

4

2 に答える 2

0

DFSは再帰的アルゴリズムです。

スタックスペースの不足を回避しようとしている場合は、明示的なスタックを使用できます（暗黙的な呼び出しスタックを明示的なノードスタックに変換します）。しかし、それが再帰的アルゴリズムであるという事実から逃れることはできないと思います。

明示的なスタックを使用している場合でも、メモリが不足する可能性があります。これは、システムのメモリ量とツリーの形状によって異なります。ただし、ほとんどの場合、少なくとも厄介なクラッシュを回避できます（ヒープメモリが不足したときに検出できます）。

于 2012-02-19T22:04:56.447 に答える
0

最後に私はそれを理解しました。それほど速くはないかもしれませんが、メモリをあまり消費せずにテストに合格するのに十分な速度です。子供から父親へのポインター（ojciecと呼ばれる8 MBの配列）が必要で、ノードが初めてアクセスされたか（下降）、そうでないか（上昇）を検出しました。これが私のコードです：

void dfs()
{
  int preorder = 0;
  int i;
  stack<int, list<int> > stos;

  stos.push(1);
  while(!stos.empty()) {
    i = stos.top();

    if (order[i] == 0) { // node is first time visited
      order[i] = ++preorder; // set default values
      size[i]  = 1;
    }

    if (dynastia[i] != NULL) // can go left...
      stos.push( pop( &dynastia[i] ) ); // so take first child, remove it and release memory
    else {
      stos.pop();
      size[ojciec[i]] += size[i]; // adding total number of descendants to father
    }
  }
}
于 2012-02-20T08:49:57.107 に答える