2
/*  
if node in the first section then P[node]=1  
if node in the beginning of some section then P[node]=T[node]  
if none then P[node]=P[T[node]]  
*/
#define SIZE 102
int T[SIZE];//the father of node i in the tree
int L[SIZE];//level of the node i
int P[SIZE];//lowest ancestor of the node from the prev. section
//pre-process p using DFS
int N;
int nr;//sqrt(H)
list<int>Child[SIZE];
list<int>::iterator it;

 void dfs(int node)
    {
        if(L[node]<nr)
            P[node]=1;
            else
                {
                    if(L[node]%nr==0)//SEG-FAULT here node=6316144
                         P[node]=T[node];
                         else
                             P[node]=P[T[node]];
                 }
            //for each son k of node
         for(it=Child[node].begin();it!=Child[node].end();it++)
              {
                 dfs(*it);
              }
    }

//here's the code to initialize L and nr
int initialize()
  {
    //initialize the L array and the nr value by finding out value of H
    int root,i;
    for(i=1;i<=N;i++)
      {
        if(T[i]==-1)
          {
            root=i;
            break;
          }
      }
    queue<int>Q;
    queue<int>t;
    t.push(root);
    int s,l=0;//nodes at the same level


    //process all the nodes in the Q at this moment
     while(!t.empty())        
     {
       while(!t.empty())
        {
            s=t.front();
            t.pop();

            L[s]=l;
            Q.push(s);
        }   
        while(!Q.empty())
        {
           s=Q.front();
           Q.pop();
           for(it=Child[s].begin();it!=Child[s].end();it++)//children of node s
             t.push(*it);
        }
        l++;
     }  



    int height=l;
    nr=sqrt(height);
    return root;
}

//here's the code to obtain the tree
void getTree()
{
   // printf("\nHow many nodes?");
     scanf("%d",&N);
   //printf("\nNow enter the tree as parent #children children");
     int i,n,p,j,c;
     for(i=0;i<=N;i++)
         T[i]=-1;//all the nodes do not have parents
     for(i=0;i<N;i++)
       {
         scanf("%d%d",&p,&n);
           for(j=0;j<n;j++)
             {
               scanf("%d",&c);
               Child[p].push_back(c);//child is pushed in the correct parent's list
               T[c]=p;//parent is updated
             }
       }
 }

上記は、LCA (Lowest Common Ancestor) 問題を解決するために P 配列を設定する単純なコードです (topcoder の記事から)。nr=sqrt(H) (別の関数を使用して評価)。リスト Child のグローバル配列には、ノードの子のインデックスが含まれます。ノードがリーフの場合、一部のリストは空です。L 配列には、BFS を使用して初期化されたノード (0 ベース) のレベルが含まれています (これは正しいです)。問題は、入力が与えられ、dfs(r)(ルート)が呼び出されるたびにセグメンテーション違反が発生し、示された行のノードの値が 6316144 と表示されることです。何が問題なのか理解できません...

4

0 に答える 0