第十五章 GRL_5_A:Diameter of a Tree 樹的直徑

知識點

直徑：樹的最遠結點間的距離

問題連結

GRL_5_A:Diameter of a Tree

問題内容

求出樹的直徑

思路

1、任選一結點s，求到s最遠的結點x

2、求到x最遠結點y

報告結點x與結點y的距離，即樹的直徑

代碼

#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>
using namespace std;
const int maxx = ;
const int INF =  << ;

class Edge {
public:
    int t, w;
    Edge() {};
    Edge(int t ,int w):t(t), w(w) {};
};
vector<Edge> G[maxx];
int n, d[maxx];
bool vis[maxx];
int cnt;

void bfs(int s) {
    for (int i = ; i < n; i++)
        d[i] = INF;
    queue<int> Q;
    Q.push(s);
    d[s] = ;

    while (!Q.empty()) {
        int u = Q.front(); Q.pop();
        int len = G[u].size();
        for (int i = ; i < len; i++) {
            Edge e = G[u][i];
            if (d[e.t] == INF) {
                d[e.t] = d[u] + e.w;
                Q.push(e.t);
            }
        }

    }

}

void solve() {
    // 從任選的結點s出發，選擇距離s最遠的結點tgt
    bfs();

    int maxv = , tgt = ;
    for (int i = ; i < n; i++) {
        if (d[i] == INF)
            continue;
        if (maxv < d[i]) {
            maxv = d[i];
            tgt = i;
        }
    }


    //從tgt出發，求結點tgt到最遠結點的距離maxv
    bfs(tgt);
    maxv = ;
    for (int i = ; i < n; i++) {
        if (d[i] == INF)
            continue;
        maxv = max(maxv, d[i]);
    }
    printf("%d\n", maxv);
}
int main() {

    int s, t, w;
    scanf("%d", &n);
    for (int i = ; i < n - ; i++) {
        scanf("%d %d %d", &s, &t, &w);
        // 無向圖
        G[s].push_back(Edge(t, w));
        G[t].push_back(Edge(s, w));
    }
    solve();
    return ;
}