"Hello World!" in C

  • + 0 comments
    #include <iostream>
    #include <vector>
    #include <queue>
    using namespace std;
    
    vector<vector<int>> tree;
    vector<int> dist;
    
    void bfs(int start, int &farthest) {
        queue<int> q;
        q.push(start);
        dist[start] = 0;
        while (!q.empty()) {
            int node = q.front();
            q.pop();
            for (int neighbor : tree[node]) {
                if (dist[neighbor] == -1) {
                    dist[neighbor] = dist[node] + 1;
                    q.push(neighbor);
                    if (dist[neighbor] > dist[farthest]) farthest = neighbor;
                }
            }
        }
    }
    
    int longestPath(int n) {
        dist.assign(n + 1, -1);
        int farthest = 1;
        bfs(1, farthest);
        dist.assign(n + 1, -1);
        bfs(farthest, farthest);
        return dist[farthest];
    }
    
    int main() {
        int n, u, v;
        cin >> n;
        tree.assign(n + 1, vector<int>());
        for (int i = 0; i < n - 1; i++) {
            cin >> u >> v;
            tree[u].push_back(v);
            tree[v].push_back(u);
        }
        cout << longestPath(n);
        return 0;
    }