Cod sursa(job #2567528)

Utilizator i.uniodCaramida Iustina-Andreea i.uniod Data 3 martie 2020 17:43:39
Problema Diametrul unui arbore Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.91 kb
#include <fstream>
#include <vector>
#include <cstring>
using namespace std;

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

const int N_MAX = 1e5 + 5;
int v[N_MAX], N;
bool vis[N_MAX];
vector <int> G[N_MAX];

void DFS(int start) {
    vis[start] = true;
    for(auto it : G[start])
        if(vis[it] == false) {
            v[it] = v[start] + 1;
            DFS(it);
        }
}

int main()
{
    fin >> N;
    for(int i = 1; i < N; i++) {
        int x, y;
        fin >> x >> y;
        G[x].push_back(y);
        G[y].push_back(x);
    }

    v[1] = 1;
    DFS(1);

    int node, maxim = -1;
    for(int i = 1; i <= N; i++)
        if(maxim < v[i]) {
            maxim = v[i];
            node = i;
        }

    memset(v, 0, sizeof(v));
    memset(vis, 0, sizeof(vis));

    v[node] = 1;
    DFS(node);

    maxim = -1;
    for(int i = 1; i <= N; i++)
        maxim = max(maxim, v[i]);

    fout << maxim;
    return 0;
}