Cod sursa(job #2166324)

Utilizator stefii_predaStefania Preda stefii_preda Data 13 martie 2018 16:36:47
Problema Diametrul unui arbore Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.01 kb
#include <fstream>
#include <vector>

using namespace std;

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

const int N = 100005;

vector <int> g[N];
int n, c[N], d[N], departe;
bool viz[N];


void bfs(int nod)
{
    for(int i = 1; i <= n; i++)
    {
        d[i] = 0;
        viz[i] = false;
    }
    int p = 1, u = 1;
    c[1] = nod;
    viz[nod] = true;
    d[nod] = 1;
    while( p <= u )
    {
        nod = c[p];
        p ++;
        for(int i = 0; i < g[nod].size(); i++)
        {
            if(viz[g[nod][i]] == false)
            {
                viz[g[nod][i]] = true;
                u++;
                c[u] = g[nod][i];
                d[g[nod][i]] = d[nod] + 1;
            }
        }
    }
    departe = nod;

}


int main()
{
    in >> n ;
    int i, a, b;
    for(i = 1; i < n; i++)
    {
        in >> a >> b;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    bfs(1);
    bfs(departe);
    out << d[departe];


    return 0;
}