Cod sursa(job #1921253)

Utilizator jason2013Andronache Riccardo jason2013 Data 10 martie 2017 11:54:37
Problema Diametrul unui arbore Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.87 kb
#include<bits/stdc++.h>
using namespace std;

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

const int N_MAX = 100010;

int N, length[N_MAX], last;
vector<int>G[N_MAX];
deque<int>Q;

void read()
{
    in >> N;
    while( N -- )
    {
        int x, y;
        in >> x >> y;
        G[x].push_back(y);
        G[y].push_back(x);
    }
}

void bfs(const int start)
{
    Q.push_back(start);
    memset(length, 0, sizeof(length));
    length[start] = 1;
    while(!Q.empty())
    {
        int node = Q.front();
        last = node;
        Q.pop_front();
        for(auto &son : G[node])
            if(length[son] == 0)
            {
                length[son] = length[node] + 1;
                Q.push_back(son);
            }
    }
}

int main()
{
    read();
    bfs(1);
    bfs(last);

    out << length[last];
    return 0;
}