This topic is in the tree data structure, but actually with the figure is more simple, Freud algorithm can quickly do it, is to eat triple cycle comparison time complexity, compared with the algorithm bosses in a variety of LCA problem solving, I saw the university just began to learn programming shivering (my last semester is mentality explosion to autism), I am here on the basis of the school of problem solving.

The title

code

#include <stdio.h>
#include <stdlib.h>

#defineMin(a,b) ((a)<(b)? (a):(b))// Hand beat min to improve efficiency
#defineMax(a,b) ((a)>(b)? (a):(b))// As above, remember not to omit parentheses


struct graphList
{
    int vexNum;
    int graph[120] [120];
};

void createNewGraphList(struct graphList *gList,int Num)
{
    int i,j;
    int x,y;
    gList->vexNum=Num;
    for(i=1; i<=Num; i++)for(j=1; j<=Num; j++)/ / initialization
    {
       if(i! =j) gList->graph[i][j]=1000;
       else gList->graph[i][j]=0;
    }

    for(i=1; i<=Num- 1; i++) {scanf("%d %d",&x,&y);
       gList->graph[x][y]=1;// The distance between father and child is 1
       gList->graph[y][x]=2;// The distance between the child and its father is 2}}void floydAlgorithm(struct graphList *gList)
{
      int v,w,k;
    // This is the core of Freud's algorithm
    //k is the intermediate point
    for(k=1; k<=gList->vexNum; k++) {/ / v as a starting point
         for(v=1; v<=gList->vexNum; v++) {/ / w to the end
             for(w=1; w<=gList->vexNum; w++) {if(gList->graph[v][w]>gList->graph[v][k]+gList->graph[k][w])
                 {
                     gList->graph[v][w]=gList->graph[v][k]+gList->graph[k][w];// Update the minimum path
                 }
             }
         }
    }
}

void FindDepthAndWidth(struct graphList *gList)
{
     int maxsum=0,maxd=0,maxn=1;
     int b[1000];
    for(int i=2; i<=gList->vexNum; i++) { maxsum=Max(maxsum,gList->graph[1][i]);/ / depth
        b[gList->graph[1][i]]++;// Count the number of nodes in each layer
        maxn=Max(maxn,gList->graph[i][1]);
    }
    for(int i=1; i<=maxn; i++) maxd=Max(maxd,b[i]);/ / width

    printf("%d\n%d\n",maxsum+1,maxd);
}

int main(a)
{
    struct graphList gList;
    int x,y,Num;
    scanf("%d",&Num);
    createNewGraphList(&gList,Num);
    floydAlgorithm(&gList);
    scanf("%d %d",&x,&y);
    FindDepthAndWidth(&gList);
    printf("%d",gList.graph[x][y]);
    return 0;
}

Copy the code

Test;