Cod sursa(job #2834094)

Utilizator paul911234vaida paul paul911234 Data 16 ianuarie 2022 14:03:14
Problema Diametrul unui arbore Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.39 kb
#include <iostream>
#include <vector>
#include <queue>
#include <fstream>
using namespace std;

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

#define MAX_N 100001

vector<vector<int>> tree(MAX_N);

int diameter;

int BFS(int begin) {
    vector<bool> visited(MAX_N);
    queue<int> myQueue;
    int last;
    myQueue.push(begin);
    while (!myQueue.empty()) {
        int element = myQueue.front();
        for (int i = 0; i < tree[element].size(); ++i) {
            if (visited[tree[element][i]] == false) {
                visited[tree[element][i]] = true;
                myQueue.push(tree[element][i]);
                last = tree[element][i];
            }
        }
        myQueue.pop();
    }
    return last;
}//in this function, I will be looking for the most far away leaf

vector<int>visited(MAX_N);

void DFS(int node, int cnt) {
    visited[node] = true;
    if (tree[node].size() == 1 ) {
        diameter = max(cnt, diameter);
        cnt = 0;
    }
    for (int i = 0; i < tree[node].size(); ++i) {
        if (visited[tree[node][i]] == false) {
            DFS(tree[node][i], cnt + 1);
        }
    }
}

int main() {
    int n;
    fin >> n;
    for (int i = 1, x, y; i < n; ++i) {
        fin >> x >> y;
        tree[x].push_back(y);
        tree[y].push_back(x);
    }
    DFS(BFS(4), 0);
    fout << diameter + 1;
    return 0;
}