Cod sursa(job #3229450)

Utilizator Cristian243Cristian-Stefan Lazar Cristian243 Data 16 mai 2024 00:17:19
Problema Diametrul unui arbore Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.16 kb
#include <bits/stdc++.h>
#include <iostream>
using namespace std;

class Solutuion {
 private:
    size_t N;
    size_t M;
    vector<vector<size_t>> adj;

 public:
    explicit Solutuion(ifstream &in) {
        in >> N;
        adj.resize(N + 1);

        size_t node1, node2;
        for (size_t i = 1; i <= N - 1; i++) {
            in >> node1 >> node2;

            adj[node1].push_back(node2);
            adj[node2].push_back(node1);
        }
    }

    int solve() {
        vector<int> d(N + 1, -1);
        d[1] = 0;

        queue<int> q;
        q.push(1);

        int dist = 1;
        int prev_children = 1;
        int next_children = 0;

        while(!q.empty()) {
            int curr_node = q.front();
            q.pop();

            for (auto neigh : adj[curr_node]) {
                if (d[neigh] != -1)
                    continue;
                
                d[neigh] = dist;
                next_children++;
                q.push(neigh);
            }
            
            if (--prev_children == 0) {
                prev_children = next_children;
                next_children = 0;
                dist++;
            }
        }

        size_t leaf1 = distance(d.begin(), max_element(d.begin(), d.end()));

        q = queue<int>();
        q.push(leaf1);
        d = vector<int>(N + 1, -1);
        d[leaf1] = 0;

        dist = 1;
        prev_children = 1;
        next_children = 0;

        while(!q.empty()) {
            int curr_node = q.front();
            q.pop();

            for (auto neigh : adj[curr_node]) {
                if (d[neigh] != -1)
                    continue;
                
                d[neigh] = dist;
                next_children++;
                q.push(neigh);
            }
            
            if (--prev_children == 0) {
                prev_children = next_children;
                next_children = 0;
                dist++;
            }
        }

        return *max_element(d.begin(), d.end()) + 1;
    }
};

int main() {
    ifstream in("darb.in");
    ofstream out("darb.out");
    
    int solution = Solutuion(in).solve();
    out << solution << endl;
    
    in.close();
    out.close();
    return 0;
}