Cod sursa(job #3136474)

Utilizator Horia_haivasHaivas Horia Horia_haivas Data 6 iunie 2023 15:15:17
Problema Diametrul unui arbore Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.59 kb
/*
    "TLE is like the wind, always by my side"
    - Yasuo - 2022 -
*/
#include <bits/stdc++.h>
#define debug(x) cerr << #x << " " << x << "\n"
#define debugs(x) cerr << #x << " " << x << " "
#pragma GCC optimize("Ofast")

using namespace std;

struct node
{
    int val;
    int depth;
};

vector<int> nodes[100001];
queue<node> q;
bool visited[100001];

int main()
{
    ifstream fin("darb.in");
    ofstream fout("darb.out");
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n,i,j,u,v,last,mx;
    node frontnode;
    fin >> n;
    for (i=1;i<=n-1;i++)
    {
         fin >> u >> v;
         nodes[u].push_back(v);
         nodes[v].push_back(u);
    }
    q.push({1,0});
    while (!q.empty())
    {
         frontnode=q.front();
         if (!visited[frontnode.val])
         {
             visited[frontnode.val]=1;
             for (j=0;j<nodes[frontnode.val].size();j++)
             {
                  q.push({nodes[frontnode.val][j],frontnode.depth+1});
             }
             last=frontnode.val;
         }
         q.pop();
    }
    for (j=1;j<=n;j++)
    {
        visited[j]=0;
    }
    mx=-1;
    q.push({last,0});
    while (!q.empty())
    {
        frontnode=q.front();
        if (!visited[frontnode.val])
        {
            visited[frontnode.val]=1;
            for (j=0;j<nodes[frontnode.val].size();j++)
            {
                q.push({nodes[frontnode.val][j],frontnode.depth+1});
            }
            mx=max(frontnode.depth,mx);
        }
        q.pop();
    }
    fout << mx+1;
}