Cod sursa(job #1551696)

Utilizator DanFodorFODOR Dan Horatiu DanFodor Data 16 decembrie 2015 12:48:27
Problema Diametrul unui arbore Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.66 kb
#include <fstream>
#include <vector>
#include <queue>

using namespace std;

int n;
vector<int> v[100001];
int marked[100001], len[100001];
queue<int> q;
int maxlen, maxnode;

int main()
{
    ifstream cin ("darb.in");
    ofstream cout ("darb.out");

    cin >> n;

    int x, y;
    int i;

    for (i = 1; i < n; ++i)
    {
        cin >> x >> y;
        v[x].push_back(y);
        v[y].push_back(x);
    }
    q.push(1);
    marked[1] = 1;

    while (!q.empty())
    {
        int node = q.front();
        q.pop();
        for (vector<int>::iterator it = v[node].begin(); it != v[node].end(); ++it)
        {
            int k = *it;
            if (marked[k] == 0)
            {
                len[k] = len[node] + 1;
                marked[k] = 1;
                q.push(k);
                if (maxlen < len[k])
                {
                    maxlen = len[k];
                    maxnode = k;
                }
            }
        }
    }
    for (i = 1; i <= n; ++i)
    {
        len[i] = 0;
        marked[i] = 0;
    }

    q.push(maxnode);
    marked[maxnode] = 1;
    len[maxnode] = 1;
    int diameter = 0;

    while (!q.empty())
    {
        int node = q.front();
        q.pop();
        for (vector<int>::iterator it = v[node].begin(); it != v[node].end(); ++it)
        {
            int k = *it;
            if (marked[k] == 0)
            {
                marked[k] = 1;
                len[k] = len[node] + 1;
                q.push(k);
                if (diameter < len[k])
                    diameter = len[k];
            }
        }
    }

    cout << diameter;

    return 0;
}