SPOJ - PT07Z （DFS）

传送门 

题面：

You are given an unweighted, undirected tree. Write a program to output the length of the longest path

(from one node to another) in that tree. The length of a path in this case is number of edges we traverse from source to destination.

Input

The first line of the input file contains one integer N --- number of nodes in the tree (0 < N <= 10000). Next N-1 lines contain N-1 edges of that tree --- Each line contains a pair (u, v) means there is an edge between node u and node v (1 <= u, v <= N).

Output

Print the length of the longest path on one line.

Example

Input:
3
1 2
2 3

Output:
2

 题目大意就是给你一棵无权值，无向的树，求它的最长路径。

思路就是用vector储存树，然后由无向树的性质可从任意一个点进行一次DFS，在DFS的过程中记录从该节点出发的路径的最长值并返回，由于最长路径可能不会经过出发结点，于是在对每一个点进行DFS时记录子路径的最长值和次长值并与当前最长路径比较，即可得出结果。

#include <vector>
#include <stdio.h>
using namespace std;
int ans = 0;
vector <int > vec[10010];

int DFS(int node,int fa)
{
    int L = vec[node].size() , MAx = 0 , MAx1 = 0;
    for(int i = 0 ; i < L ; ++i)
    {
        if(vec[node][i] == fa) continue; //不可回退。
        int t = DFS(vec[node][i],node);
        if(t > MAx) MAx1 = MAx , MAx = t;
        else if(t > MAx1) MAx1 = t;
    }
    if(MAx + MAx1 + 1 > ans) ans = MAx + MAx1 + 1;
    return MAx + 1;
}

int main()
{
    int n,a,b;
    scanf("%d",&n);
    for(int i = 0 ; i < n - 1 ; ++i)
    {
        scanf("%d%d",&a,&b);
        vec[a].push_back(b);
        vec[b].push_back(a);
    }
    DFS(1,n+1);
    printf("%d\n",ans - 1); //最多经过节点数减1即为最长路径的长度。
    return 0;
}