Cod sursa(job #1170635)

Utilizator lucian666Vasilut Lucian lucian666 Data 13 aprilie 2014 23:01:40
Problema Diametrul unui arbore Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.01 kb



#include<fstream>
#include<vector>
#include<algorithm>
#include<queue>
#include<bitset>



#define NN 100009
#define pb push_back
using namespace std;
ofstream out("darb.out");

int n , nod_max , diametru = -0x3f3f3f3f;

vector<int>G[NN];

typedef vector<int>::iterator IT;

bitset<NN>uz;

void read();
void dfs( int , int );
void solve();


int main()
{

    read();
    solve();

    out << diametru + 1  ;





}

void read()
{


    ifstream in("darb.in");
    in >> n ;
    for( int i = 1 ; i < n  ;i++)
    {
        int x , y;
        in >> x >> y;
        G[x].pb(y);
        G[y].pb(x);
    }



}

void solve()
{

    dfs(1,0);
    uz.reset();
    dfs(nod_max,0);

}

void dfs(int root , int deep )
{

    uz[root] = 1;
    if( deep > diametru )
    {

        nod_max = root;
        diametru = deep;
    }

    for( IT i = G[root].begin() ; i != G[root].end(); ++i )
            if( !uz[*i] )
                dfs(*i,deep + 1 );
}