Cod sursa(job #2749446)

Utilizator Razvan48Capatina Razvan Nicolae Razvan48 Data 6 mai 2021 18:44:50
Problema Diametrul unui arbore Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.18 kb
#include <fstream>
#include <vector>

using namespace std;

const int NMAX = 100000;

vector<int> graf[1 + NMAX];

bool vizitat[1 + NMAX];
int cost[1 + NMAX];

void dfs(int nod)
{
    vizitat[nod] = true;

    for (int i = 0; i < graf[nod].size(); i++)
    {
        int vecin = graf[nod][i];

        if (!vizitat[vecin])
        {
            cost[vecin] = cost[nod] + 1;
            dfs(vecin);
        }
    }
}

int main()
{
    ifstream in("darb.in");
    ofstream out("darb.out");

    int n;

    in >> n;

    for (int i = 2; i <= n; i++)
    {
        int x, y;

        in >> x >> y;

        graf[x].push_back(y);
        graf[y].push_back(x);
    }

    dfs(1);

    int distMax;

    int capatDiametru = -1;
    distMax = -1;

    for (int i = 1; i <= n; i++)
    {
        if (distMax < cost[i])
        {
            capatDiametru = i;
            distMax = cost[i];
        }

        vizitat[i] = false;
        cost[i] = 0;
    }

    dfs(capatDiametru);

    distMax = -1;

    for (int i = 1; i <= n; i++)
    {
        distMax = max(distMax, cost[i]);
    }

    out << distMax + 1 << '\n';

    return 0;
}