Cod sursa(job #2258840)

Utilizator MarianConstantinMarian Constantin MarianConstantin Data 12 octombrie 2018 11:46:43
Problema Diametrul unui arbore Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.07 kb
#include <iostream>
#include <fstream>
#include <vector>
#define N 100010

using namespace std;

vector<int> edges[N];
int dist[N], n;
bool visited[N];

void dfs(int node)
{
    vector<int>::iterator it;
    for (it=edges[node].begin(); it!=edges[node].end(); it++)
    {
        if (!visited[*it])
        {
            dist[*it]=dist[node]+1;
            visited[*it]=1;
            dfs(*it);
        }
    }
}

int main()
{
    ifstream fin("darb.in");
    ofstream fout("darb.out");
    int x, y, maxValue=0, maxIndex=1;
    fin >> n;
    for (int i=0; i<n; i++)
    {
        fin >> x >> y;
        edges[x].push_back(y);
        edges[y].push_back(x);
    }
    visited[1]=1;
    dfs(1);
    for (int i=1; i<=n; i++)
    {
        if (maxValue<dist[i])
            maxValue=dist[i],maxIndex=i;
        dist[i]=0;
        visited[i]=0;
    }
    visited[maxIndex]=1;
    dfs(maxIndex);
    maxValue=0;
    for (int i=1; i<=n; i++)
        if (maxValue<dist[i])
            maxValue=dist[i];
    fout << maxValue+1;
    return 0;
}