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
             }
       }
 }

以上是填充 P 数组以解决 LCA（最低公共祖先）问题的简单代码（来自 topcoder 文章）。nr=sqrt(H)（使用另一个函数计算）。列表的全局数组 Child 包含节点的子节点的索引。如果节点是叶子，则某些列表为空。L 数组包含使用 BFS 初始化的节点的级别（基于 0）（这是正确的）。问题是每当给出输入并且dfs（r）（根）被称为分段错误时，指示行中节点的值显示为6316144。我只是不明白出了什么问题......

4

0 回答 0