Cod sursa(job #2092310)

Utilizator infomaxInfomax infomax Data 21 decembrie 2017 15:31:37
Problema Diametrul unui arbore Scor 90
Compilator cpp Status done
Runda Arhiva educationala Marime 0.8 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];
bitset<100005> v;

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

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, 0);
    for( int i = 2; i <= n; ++ i )
    {
        if( d[i] > maxx ) maxx = d[i], m = i;
        d[i] = 0;
    }
    v = 0;
    dfs(m, 1);
    maxx = -1;
    for( int i = 2; i <= n; ++ i )
        if( d[i] > maxx ) maxx = d[i];
    G << maxx;
    return 0;
}