求树中的最长路 （*【模板】代码个别地方需要根据情况修改 读懂理解后再照搬代码 ）

两次DFS求树中的最长路。

基于邻接矩阵：

代码：

#include <stdio.h>
#include <string.h>
#include <vector>
#include <iostream>
#include <string>
#include <algorithm>

using namespace std;

bool map[10001][10001];
int n;
int tail;
bool vis[1001];
int fa[1001];

void DFS_root(int dd)
{
    int i, j;
    for(i=1; i<=n; i++)
    {
        if(vis[i]==false && map[dd][i]==true )
        {
            fa[i]=fa[dd]+1;
            vis[i]=true;
            DFS_root(i);
        }
    }
    int len=0;
    tail=1;
    for(j=2; j<=n; j++)
    {
        if(fa[j]>len)
            tail=j;
    }
    //printf("%d***
", tail );
    return;
}
int len=0; //记录树中最长的路径长度
void DFS_len_tree(int dd)
{
    int i, j;
    for(i=1; i<=n; i++)
    {
        if(vis[i]==false && map[dd][i]==true )
        {
            fa[i]=fa[dd]+1; //由前一个节点的长度+1过来的
            vis[i]=true;
            DFS_len_tree(i);
        }
    }
    len=fa[1];
    for(j=2; j<=n; j++)
    {
        if(fa[j]>len)
            len=fa[j];
    }
}


int main()
{
    int i, j;
    int u, v;
    scanf("%d", &n);
    for(i=0; i<=n; i++ )
    {
        for(j=0; j<=n; j++)
        {
            map[i][j]=false;
        }
    } //map的初始化
    for(i=0; i<n-1; i++)
    {
        scanf("%d %d", &u, &v );
        map[u][v]=true;
        map[v][u]=true;
    }
    memset(vis, false, sizeof(vis));
    memset(fa, 0, sizeof(fa));
    vis[1]=true;
    DFS_root(1);

    memset(vis, false, sizeof(vis));
    memset(fa, 0, sizeof(fa)); //记录路径长度
    vis[tail]=true;
    DFS_len_tree(tail);
    printf("%d
", len );
    return 0;
}

 基于vector二维模拟邻接表：

代码：

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <string>
#include <iostream>
#include <vector>
#include <algorithm>
#define N 100002

using namespace std;
vector<int>q[N];
bool vis[N];
int fa[N];
int n, tail;
int ans;
void DFS_root(int dd)
{
    int i, j;
    int len;
    len=q[dd].size();
    for(i=0; i<len; i++)
    {
        if(vis[q[dd][i]]==false )
        {
            fa[q[dd][i]]=fa[dd]+1;
            vis[q[dd][i]]=true;
            DFS_root(q[dd][i]);
        }
    }
    len=fa[1];tail=1;
    for(j=2; j<=n; j++)
    {
        if(fa[j]>len)
        {
            len=fa[j];
            tail=j;
        }
    }
}

void DFS_len_tree(int dd)
{
    int len, i, j;
    len=q[dd].size();
    for(i=0; i<len; i++)
    {
        if(vis[q[dd][i]]==false)
        {
            fa[q[dd][i]]=fa[dd]+1;
            vis[q[dd][i]]=true;
            DFS_len_tree(q[dd][i]);
        }
    }
}

int main()
{
    int i, j;
    int u, v;
    scanf("%d", &n);
    for(i=0; i<=n; i++)
        q[i].clear();
    for(i=0; i<n-1; i++)
    {
        scanf("%d %d", &u, &v);
        q[u].push_back(v);
        q[v].push_back(u);
    }
    memset(vis, false, sizeof(vis));
    memset(fa, 0, sizeof(fa));
    vis[1]=true;
    DFS_root(1);

    memset(vis, false, sizeof(vis));
    memset(fa, 0, sizeof(fa));
    vis[tail]=true;
    DFS_len_tree(tail);

    ans=fa[1];
    for(j=2; j<=n; j++)
    {
        if(fa[j]>ans )
            ans=fa[j];
    }
    printf("%d
", ans );
    return 0;
}