Đường kính cây trong C++

Cho cây không hướng (danh sách cạnh edges[i] = [u, v]), tìm đường kính — số cạnh trên đường đi dài nhất.

Ví dụ: cây cạnh [[0,1],[1,2],[2,3],[1,4],[4,5]] → Đường kính = 4.

Giải thuật (2 lần DFS)

1. Xây đồ thị từ danh sách cạnh.
2. DFS từ nút 0 tìm nút xa nhất node.
3. DFS từ node tìm độ sâu lớn nhất → đó là đường kính.
4. DFS trả về độ sâu lớn nhất từ nút hiện tại, cập nhật best và node xa nhất.

Ví dụ C++

#include <bits/stdc++.h>
using namespace std;
#define pb push_back

class Solution {
public:
    map<int, int> l;
    int best, node;
    int dfs(int v, bool* visited, vector<int> graph[], int c = 0) {
        visited[v] = true;
        int ans = 0;
        for(int i = 0; i < graph[v].size(); i++) {
            if(!visited[graph[v][i]]) ans = max(ans, dfs(graph[v][i], visited, graph, c+1));
        }
        if(c > best) { best = c; node = v; }
        visited[v] = false;
        return max(c, ans);
    }
    int treeDiameter(vector<vector<int>>& e) {
        int n = e.size();
        vector<int> graph[n+1];
        for(int i = 0; i < n; i++) {
            graph[e[i][0]].pb(e[i][1]);
            graph[e[i][1]].pb(e[i][0]);
        }
        bool* visited = new bool[n+1]();
        best = 0; node = 0;
        dfs(0, visited, graph);
        bool* visited2 = new bool[n+1]();
        return dfs(node, visited2, graph);
    }
};

int main() {
    vector<vector<int>> v = {{0,1},{1,2},{2,3},{1,4},{4,5}};
    Solution ob;
    cout << ob.treeDiameter(v);
    return 0;
}

Đầu vào

[[0,1],[1,2],[2,3],[1,4],[4,5]]

Đầu ra

4