เส้นผ่านศูนย์กลางต้นไม้ใน C++

สมมติว่าเรามีต้นไม้แบบไม่มีทิศทาง (undirected tree) ต้องหาเส้นผ่านศูนย์กลาง (diameter) ซึ่งคือจำนวนขอบ (edges) ในเส้นทางที่ยาวที่สุดในต้นไม้นั้น ต้นไม้ให้มาในรูปรายการขอบ edges[i] = [u, v]

ตัวอย่าง กราฟดังภาพ ผลลัพธ์: 4

ขั้นตอนการแก้ปัญหา (Two-pass DFS)

• สร้างกราฟจากรายการขอบ
• DFS ครั้งแรกจากโหนด 0 หาโหนดที่ไกลที่สุด (node)
• DFS ครั้งที่สองจาก node หาระยะทางไกลที่สุด ซึ่งคือเส้นผ่านศูนย์กลาง

ตัวอย่างโค้ด (C++)

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

class Solution {
public:
    map <int ,int > l;
    int best;
    int 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);
}

อินพุต

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

เอาต์พุต

4