题目意思就是给你一棵树,保证这颗树的合法性,然后加入要你判断这棵树最长的路径是多长。这里有个小技巧就是从任意一点开始出发找到最远的一点再从这一点出发寻找最远点,之后找到的最远点就是整棵树的最远点了。


题目:http://codeforces.com/problemset/problem/690/C2


代码:

Memory: 5400 KB
Time: 108 MS
Language: GNU G++ 5.1.0
Result: Accepted
#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>
using namespace std;
#define MAX 100000+10
int dis[MAX];
int n, m, s, e;
int inf=10e6;
vector <pair<int, int> > node[MAX];
priority_queue <pair<int, int> > Q;
int init(){
    for(int i=1;i<=n;i++){
        node[i].clear();
        dis[i]=inf;
    }
    int u, v;
    for(int i=0;i<m;i++){
        scanf("%d%d", &u, &v);
        node[u].push_back(make_pair(v, 1));
        node[v].push_back(make_pair(u, 1));
        if(!i)s=u;
    }
    dis[s] = 0;
    Q.push(make_pair(-dis[s], s));
}
int maxp(){
    while(!Q.empty())
    {
        int u=Q.top().second;
        Q.pop();
        for(int i=0;i<node[u].size();i++)
        {
            int v=node[u][i].first;
            if(dis[v]>dis[u]+node[u][i].second)
            {
                dis[v]=dis[u]+node[u][i].second;
                Q.push(make_pair(-dis[v], v));
            }
        }
    }
    int td=0, ti=0;
    for(int i=1;i<=n;i++){
        if(dis[i]!=inf && dis[i]>td){
            td = dis[i];
            ti = i;
        }
    }
    return ti;
}
int main(){
    while(~scanf("%d%d", &n, &m)){
        init();
        e = maxp();
        for(int i=1;i<=n;i++)dis[i]=inf;
        s = e;
        dis[s] = 0;
        while(!Q.empty())Q.pop();
        Q.push(make_pair(-dis[s], s));
        e = maxp();
        cout<<dis[e]<<endl;
    }
    return 0;
}