Cod sursa(job #3234945)

Utilizator Octa-pe-infoNechifor Octavian Octa-pe-info Data 12 iunie 2024 19:50:20
Problema Diametrul unui arbore Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.51 kb
#include <iostream>
#include <vector>
#include <fstream>
using namespace std;

ifstream fin("darb.in");
ofstream fout("darb.out");

vector<vector<int>> tabel;
vector<bool> viz;
vector<int> d1, d2;
pair<int, int> maxi; // first == cost, second == node

void dfs1(int node) {
    viz[node] = true;

    for (auto i : tabel[node]) {
        if (viz[i] == false) {
            d1[i] = d1[node] + 1;
            if (d1[i] > maxi.first) {
                maxi.first = d1[i];
                maxi.second = i;
            }
            dfs1(i);
        }
    }
}

void dfs2(int node) {
    viz[node] = true;

    for (auto i : tabel[node]) {
        if (viz[i] == false) {
            d2[i] = d2[node] + 1;
            if (d2[i] > maxi.first) {
                maxi.first = d2[i];
                maxi.second = i;
            }
            dfs2(i);
        }
    }
}

int main() {
    int n;
    fin >> n;

    tabel.resize(n + 1);
    d1.resize(n + 1, 0);
    viz.resize(n + 1);
    d2.resize(n + 1, 0);

    for (int i = 1; i < n; i++) {
        int x, y;
        fin >> x >> y;

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

    // Prima căutare DFS
    fill(viz.begin(), viz.end(), false);
    maxi.first = 0;
    dfs1(1); // Update maxi

    // A doua căutare DFS
    fill(viz.begin(), viz.end(), false);
    maxi.first = 0;
    dfs2(maxi.second); // Vedem unde e diametrul

    fout << maxi.first + 1; // Diametrul, ca numar de noduri

    return 0;
}