Cod sursa(job #2092325)

Utilizator infomaxInfomax infomax Data 21 decembrie 2017 15:46:09
Problema Diametrul unui arbore Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.76 kb
#include <fstream>
#include <vector>
#include <bitset>

using namespace std;

ifstream F("darb.in");
ofstream G("darb.out");

int x, y, n, m, maxx, d[100005];
vector<int> a[100005];

void dfs(int x, int t)
{
    d[x] = d[t] + 1;
    vector<int> :: iterator it;
    for(it = a[x].begin(); it != a[x].end(); ++ it)
        if( !d[*it] ) dfs(*it, x);
}

int main()
{
    F >> n;
    for( int i = 1; i < n; ++ i )
    {
        F >> x >> y; a[x].push_back(y); a[y].push_back(x);
    }
    dfs(1, 1);
    for( int i = 1; i <= n; ++ i )
    {
        if( d[i] > maxx ) maxx = d[i], m = i;
        d[i] = 0;
    }
    dfs(m, m);
    maxx = -1;
    for( int i = 1; i <= n; ++ i )
        if( d[i] > maxx ) maxx = d[i];
    G << maxx;
    return 0;
}