Cod sursa(job #1479900)

Utilizator cristian.caldareaCaldarea Cristian Daniel cristian.caldarea Data 1 septembrie 2015 16:45:33
Problema Diametrul unui arbore Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.16 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
using namespace std;

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

int n, l;
queue<int> q;

vector<vector<int>> g;
vector<bool> v,b ;

void Bfs();
void Read();
int Dfs(int x);

int main()
{
    Read();
    Bfs();
    fout << Dfs(l);
    return 0;
}

void Read()
{
    fin >> n;

    g = vector<vector<int>>(n+1, vector<int>());
    v = vector<bool>(n+1);
    b = vector<bool>(n+1);
    int x, y;
    while ( fin >> x >> y )
    {
        g[y].push_back(x);
        g[x].push_back(y);
    }

}

void Bfs()
{
    q.push(1);
    v[1] = 1;
    int x;
    while(!q.empty())
    {
        x = q.front();
        q.pop();
        for ( auto y : g[x] )
        {
            if ( !v[y] )
            {
                q.push(y);
                v[y] = 1;
            }
        }
        if ( q.empty())
        {
            l = x;
        }
    }

}

int Dfs(int x)
{
    b[x] = 1;
    int z = 0;
    for ( auto y : g[x] )
    {
        if ( !b[y] )
        {
            z = max ( z, Dfs(y));
        }
    }
    return z + 1;
}