Cod sursa(job #1885100)

Utilizator remus88Neatu Remus Mihai remus88 Data 19 februarie 2017 16:59:34
Problema Diametrul unui arbore Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.44 kb
#include <fstream>
#include <vector>
#include <queue>
#define Nmax 100009
#define INF (1<<30)
#include <bitset>

using namespace std;
ifstream f("darb.in");
ofstream g("darb.out");

int n,d[Nmax],x,y;
vector <int> G[Nmax];
queue <int> Q;
bitset <Nmax> inQ;

void Bfs(int source)
{
    for (int i=1; i<=n; ++i)
        d[i]=INF;
    d[source]=0;
    Q.push(source);
    while (!Q.empty())
    {
        int node=Q.front();
        Q.pop();
        for (auto x : G[node])
            if (d[x]>d[node]+1)
            {
                d[x]=d[node]+1;

                if (inQ[x]==0)
                {
                    inQ[x]=1;
                    Q.push(x);
                }
            }
    }
}

void ReadInput()
{
    f>>n;
    for (int i=1; i<n; ++i)
    {
        f>>x>>y;
        G[x].push_back(y);
        G[y].push_back(x);
    }
}

void Solve()
{
    Bfs(1);
    int maxx=0, node=0;
    for (int i=1; i<=n; ++i)
        if (d[i]==INF) d[i]=-1;
    for (int i=1; i<=n; ++i)
    {
        if (maxx<d[i])
        {
            maxx=d[i];
            node=i;
        }
        inQ[i]=0;
        d[i]=0;
    }
    Bfs(node);
    for (int i=1; i<=n; ++i)
        if (d[i]==INF) d[i]=-1;
    maxx=0;
    for (int i=1; i<=n; ++i)
        if (maxx<d[i])
            maxx=d[i];
    g<<maxx+1<<'\n';
}

int main()
{
    ReadInput();
    Solve();
    f.close();
    g.close();
    return 0;
}