Cod sursa(job #2206345)

Utilizator AcuasPopescu Nicolae-Aurelian Acuas Data 22 mai 2018 13:01:00
Problema Diametrul unui arbore Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.69 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
using namespace std;

void read(int &n, vector<vector<int>> &G) {
    ifstream fin("darb.in");
    if (!fin.is_open()) {
        cout << "The file can't be opened!\n";
        exit(EXIT_FAILURE);
    }

    fin >> n;
    G.resize(n + 1);
    for (int i = 0; i < n - 1; ++i) {
        int x, y;
        fin >> x >> y;
        G[x].emplace_back(y);
        G[y].emplace_back(x);
    }

    fin.close();
}

void elimin(int n, const vector<vector<int>> &G) {
    queue<int> Q;
    vector<int> viz(n + 1, 0);
    vector<int> d(n + 1, 0); //degree
    for (int i = 1; i <= n; ++i) {
        if (G[i].size() == 1) {
            viz[i] = 1;
            Q.push(i);
        }
        d[i] = G[i].size();
    }

    ofstream fout("darb.out");
    if (n == 1) {
        fout << 1 << '\n';
    }
    int r = 0, diam = 0;
    while (n >= 3) {
        int nrTerm = Q.size();
        r += 1;
        diam += 2;
        for (int i = 1; i <= nrTerm; ++i) {
            int u = Q.front();
            n--;
            d[u]--;
            Q.pop(); //elimina nodul terminal u din coada
            //Gaseste vecinul nodului u
            int vec = 0;
            for (auto v : G[u]) {
                if (viz[v] == 0) {
                    vec = v;
                    break;
                }
            }
            --d[vec];
            if (d[vec] == 1) {
                Q.push(vec);
                viz[vec] = 1;
            }

        }
    }

    if (n == 1) {
        fout << diam + 1<< '\n';
    }
    else if (n == 2) {

        fout << diam + 2 << '\n';
    }
}

int main() {
    int n;
    vector<vector<int>> G;
    read(n, G);
    elimin(n, G);
    return 0;
}