Cod sursa(job #2487793)

Utilizator EduardTudosaEduard Bogdan EduardTudosa Data 5 noiembrie 2019 18:47:57
Problema Diametrul unui arbore Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.24 kb
#include <fstream>
#include <vector>
#include <bits/stdc++.h>
#include <queue>

using namespace std;

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

int n , m , x , y , s;

queue <int> Q;
vector <int> G[100001];
bool viz[100001];
int lg[100001] , lgmax , k;

void bfs(int nod)
{
    Q.push(nod);
    while(!Q.empty())
    {
        int curent = Q.front();
        Q.pop();
        for(vector <int> :: iterator it = G[curent].begin() ; it != G[curent].end() ; it ++)
            if(!viz[*it])
            {
                lg[*it] = lg[curent] + 1;
                if(lgmax < lg[*it])
                {
                    lgmax = lg[*it];
                    k = *it;
                }
                viz[*it] = 1;
                Q.push(*it);
            }
    }
}

int main()
{
    fin >> n;
    while(fin >> x >> y)
    {
        G[x].push_back(y);
        G[y].push_back(x);
    }
    viz[1] = 1;
    bfs(1);
    memset(viz , 0 , n + 1);
    for(int i = 1 ; i <= n ; i ++)
        lg[i] = 0;
    lgmax = 0;
    viz[k] = 1;
    bfs(k);
    for(int i = 1 ; i <= n ; i ++)
        if(lg[i] > lgmax)
            lgmax = lg[i];
    fout << lgmax + 1;
    fin.close();
    fout.close();
    return 0;
}