树的直径求法,两边bfs,从任意一个点出发求出最长距离的终点,然后再从终点出发求出新的最长路,就是树的直径了。
#include <bits/stdc++.h>
using namespace std;
const int N = 10010;
typedef pair<int, int> P; // first是下一个点,second是从当前点到下一个点的距离
int dis[N]; // 保存从起点到其他点的距离
int used[N]; // 标记点是否走过
int ans = 0;
vector<P> G[N]; // 邻接表存图(树)
int bfs(int x)
{
memset(dis, 0, sizeof(dis));
memset(used, 0, sizeof(used));
queue<int> que;
que.push(x);
used[x] = 1;
int poi = 0;
while(!que.empty())
{
int v = que.front(); que.pop();
if(dis[v] > ans) //
{
ans = dis[v];
poi = v;
}
P p;
for(int i=0; i<G[v].size(); i++)
{
p = G[v][i];
if(used[p.first] == 0)
{
used[p.first] = 1;
dis[p.first] = dis[v] + p.second;
que.push(p.first);
}
}
}
return poi;
}
int main()
{
int a, b, c;
char ch;
while(scanf("%d %d %d", &a, &b, &c) != EOF)
{
G[a].push_back(P(b, c)); // 两种写法等效
G[b].push_back(make_pair(a, c));
}
ans = 0;
int point = bfs(1);
ans = 0;
bfs(point);
printf("%d\n", ans);
return 0;
}