Cod sursa(job #2008097)

Utilizator FrequeAlex Iordachescu Freque Data 5 august 2017 12:29:30
Problema Diametrul unui arbore Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.88 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <cstring>

using namespace std;

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

const int NMAX = 100000 + 5;

vector <int> graph[NMAX];

int n, v, max_depth;
bool vis[NMAX];

void read()
{
    int a, b;

    fin >> n;

    for (int i = 1; i < n; ++i)
    {
        fin >> a >> b;
        graph[a].push_back(b);
        graph[b].push_back(a);
    }
}

void dfs(int node, int parent, int depth)
{
    if (depth > max_depth)
    {
        max_depth = depth;
        v = node;
    }

    vis[node] = true;

    for (int i = 0; i < graph[node].size(); ++i)
        if (!vis[graph[node][i]])
            dfs(graph[node][i], node, depth + 1);


}

int main()
{
    read();
    dfs(1, 1, 1);
    memset(vis, 0, sizeof(vis));
    dfs(v, v, 1);
    fout << max_depth;

    return 0;
}