题目链接

题目大意

给定一个无向图，这个无向图满足其为一棵树，求树的直径的最大值

解题思路

随便找一个点进行bfs，找到距离这个点最远的点。用这个最远的点作为起点，进行bfs，此时找到最远点距离起点的值，即为直径。

代码实现

#include<iostream>
#include<cstdio>
#include<vector>
#include<queue>
#include<algorithm>
#include<cstring>
using namespace std;

const int inf = 0x3f3f3f3f;
const int N = 4e4+7;
int T;
int n,m;
int vis[N],dis[N];
struct Edge{
    int to,v;
};
vector<Edge> v[N];
queue<int> q;

void bfs(int st){
    for(int i = 1; i <= n; i++) vis[i] = 0;
    for(int i = 1; i <= n; i++) dis[i] = inf;
    while(!q.empty()) q.pop();
    q.push(st);
    vis[st] = 1;
    dis[st] = 0;
    while(!q.empty()) {
        int u = q.front();
        q.pop();
        int sz = v[u].size();
        Edge uu;
        for(int i = 0 ; i < sz; i++) { //for(auto i : v[u])
            uu=v[u][i];
            if(!vis[uu.to]) {
                vis[uu.to] = 1;
                dis[uu.to] = min(dis[u] + uu.v , dis[uu.to]);
                q.push(uu.to);
            }
        }
    }
}

int main(){
    cin>>n>>m;
    char no_use_;
    int from_, to_, v_;
    Edge qwq;
    for(int i = 1 ; i <= m ; i++) {
        scanf("%d %d %d %c",&from_,&to_,&v_,&no_use_);
        qwq.to=to_,qwq.v=v_;
        v[from_].push_back(qwq);
        qwq.to=from_,qwq.v=v_;
        v[to_].push_back(qwq);
    }
    bfs(1);
    int ww;
    int max_len = 0;
    for(int i = 1; i <= n; i++) {
        if(dis[i] > max_len) {
            max_len = dis[i];
            ww = i;
        }
    }
    bfs(ww);
    max_len = 0;
    for(int i = 1; i <= n; i++) {
        if(dis[i] > max_len) {
            max_len = dis[i];
        }
    }
    cout<<max_len<<endl;
    return 0;
}