Cod sursa(job #2470074)

Utilizator baltoi.teodorTeodor Baltoi baltoi.teodor Data 8 octombrie 2019 17:53:41
Problema Diametrul unui arbore Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.42 kb
#include <bits/stdc++.h>
#define ff first
#define ss second
#define NMAX 100005
#define pb push_back
using namespace std;
const string file = "darb";

ifstream fin (file+".in");
ofstream fout (file+".out");
typedef long long ll;
typedef long double ld;

const ll INF = 9223372036854775807ll;
const int dx[] = {1, -1, 0, 0}, dy[] = {0, 0, 1, -1}, inf = 2147483647;
int d[NMAX];
vector <int> v[NMAX];
queue<int> Q;
bool viz[NMAX];
void bfs(int x)
{
    int nod;
    d[x]=0;
    viz[x]=1;
    Q.push(x);
    while(Q.size())
    {
        nod=Q.front();
        Q.pop();
        viz[nod]=0;
        for(auto vecin:v[nod])
        {
            if(d[vecin]==-1) {
                d[vecin]=d[nod]+1;
                viz[vecin]=1;
                Q.push(vecin);
            }
            else{
                if(d[vecin]>d[nod]+1)
                {
                    d[vecin]=d[nod]+1;
                    if(!viz[vecin]) Q.push(vecin), viz[vecin]=1;
                }
            }
        }
    }
}
int main()
{
    int N, poz,x,y;
    fin>>N;

    for(int i=1;i<N;++i)
        fin>>x>>y, v[x].pb(y), v[y].pb(x), d[i]=-1;
    d[N]=-1;
    bfs(1);
    int max1=0;
    for(int i=1;i<=N;++i)
        if(d[i]>max1) max1=d[i], poz=i;

    for(int i=1;i<=N;++i)
        d[i]=-1, viz[i]=0;
    bfs(poz);
    max1=0;
    for(int i=1;i<=N;++i)
        if(d[i]>max1) max1=d[i];
    fout<<max1+1<<"\n";
    return 0;
}