Cod sursa(job #3215869)

Utilizator Dddarius95Darius-Florentin Neatu Dddarius95 Data 15 martie 2024 13:54:05
Problema Diametrul unui arbore Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.74 kb
#include <fstream>
#include <queue>
#include <utility>
#include <vector>

/**
 * A tree data structure.
*/
class Tree {
public:
    /**
     * Construct a tree with n nodes
     * @param n the number of nodes
    */
    void read(std::ifstream& in) {
        in >> n;
        adj.resize(n);

        for (int i = 1; i < n; ++i) {
            int x, y;
            in >> x >> y;
            // prefer 0-indexed nodes
            x--; 
            y--;

            adj[x].push_back(y);
            adj[y].push_back(x);
        }
    }

    /*
     * Compute the diameter of the tree
     * @return the diameter of the tree
    */
    int diameter() const {
        const auto [_, x] = bfs(0); // ignore the distance, we only need the node with the maximum distance from the source
        const auto [d, __] = bfs(x); // ignore the node, we only need the distance
        return d;
    }

private:
    /**
     * Perform a BFS starting from a given node
     * @param source the source node
     * @return a pair (d, x) where d is the maximum distance from source to any other node and x is the node with the maximum distance from source
    */
    std::pair<int, int> bfs(int source) const {
        std::vector<int> dist(n, -1); // dist[node] = -1 means node is not visited yet, otherwise it is the distance from source to node
        
        std::queue<int> q; // used to perform BFS
        q.push(source);
        dist[source] = 0;
        // compute distances from source to all other nodes
        while (!q.empty()) {
            const auto node = q.front();
            q.pop();

            for (const auto& neigh : adj[node]) {
                if (dist[neigh] == -1) {
                    dist[neigh] = dist[node] + 1;
                    q.push(neigh);
                }
            }
        }

        // find the node with the maximum distance from source
        const auto it = std::max_element(dist.begin(), dist.end());
        return { *it + 1, static_cast<int>(it - dist.begin())};
    }

    int n; // number of nodes
    std::vector<std::vector<int>> adj; // adjacency list: adj[ node ] = { x1, x2, ... }, where x1, x2, ... are the neighbors of node
};

int main() {
    std::ifstream in("darb.in");
    std::ofstream out("darb.out");


    Tree tree;
    tree.read(in);  
    out << tree.diameter() << '\n';

    in.close(); 
    out.close();

    // for (const auto& [n, superprimes] : tests) {
    //     const auto result = generateAndCountSuperPrimes(n);
    //     if (superprimes == result) {
    //         std::cerr << "Test OK: n = " << n << " (superprimes  = " << superprimes << ")" << std::endl;
    //     } else {
    //         std::cerr << "Test Failed: " << n << " expected " << superprimes << " got " << result << std::endl;
    //     }
    // }


    return 0;
}