Cod sursa(job #2570394)

Utilizator PatriciaCretoiuCretoiu Patricia PatriciaCretoiu Data 4 martie 2020 16:37:11
Problema Diametrul unui arbore Scor 100
Compilator cpp-64 Status done
Runda r3capitusulare Marime 0.92 kb
#include <bits/stdc++.h>

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

const int N = 1e5 + 5;
int n, i, a, b, ans, start, x, d[N];
bitset<N>viz;
queue<int>q;
vector<int>G[N];

void bfs(int nod)
{
    ans = 0;

    for(int i = 1; i <= n; i++)
        viz[i] = 0;

    d[nod] = 1;
    viz[nod] = 1;
    q.push(nod);

    while(!q.empty())
    {
        x = q.front();
        vector<int>::iterator it;
        for(it = G[x].begin(); it < G[x].end(); it++)
            if(!viz[*it])
        {
            d[*it] = d[x] + 1;
            if(d[*it] > ans) ans = d[*it];
            viz[*it] = 1;
            q.push(*it);
        }
        q.pop();
    }
    start = x;
}

int main()
{
    in >> n;

    for(i = 0; i < n; i++)
    {
        in >> a >> b;
        G[a].push_back(b);
        G[b].push_back(a);
    }

    bfs(1);


    bfs(start);

    out << ans;
}