Cod sursa(job #1917997)

Utilizator stefii_predaStefania Preda stefii_preda Data 9 martie 2017 13:51:14
Problema Diametrul unui arbore Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.24 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 dmax, pmax, n;
int c[N], d[N];
bool viz[N];

void bfs(int start)
{
    for(int i = 1; i <= n; i++)
    {
        c[i] = 0;
        d[i] = 0;
        viz[i] = false;
    }
    dmax = 1;
    int p = 1, u = 1, x;
    d[start] = 1;
    viz[start] = true;
    c[1] = start;
    vector <int> :: iterator it;
    while(p <= u)
    {
        x = c[p];
        p++;
        for(it = g[x].begin(); it < g[x].end(); ++it)
        {
            if(viz[*it] == false)
            {
                {
                    viz[*it] = true;
                    u++;
                    c[u] = *it;
                    d[*it] = d[x] + 1;
                    if(d[*it] > dmax)
                    {
                        dmax = d[*it];
                        pmax = *it;
                    }
                }
            }
        }
    }

}

int main()
{
    in >> n;
    int i, x, y;
    for(i = 1; i < n; i++)
    {
        in >> x >> y;
        g[x].push_back(y);
        g[y].push_back(x);
    }
    bfs(1);
    bfs(pmax);
    out << dmax;

    return 0;
}