Cod sursa(job #3218398)

Utilizator AlexMihAlexandru Mihailescu AlexMih Data 27 martie 2024 09:51:02
Problema Diametrul unui arbore Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.02 kb
#include <fstream>
#include <vector>

using namespace std;

ifstream f("darb.in");
ofstream g("darb.out");

struct max_depth{
    int depth, nod;
}nod1, nod2;

bool viz[100001];
vector<int> v[100001];

void init(int n)
{
    int i;
    for(i = 1; i <= n; i++)
    {
        viz[i] = 0;
    }
}

void dfs(int nod, int tata, int depth)
{
    int i;
    viz[nod] = 1;
    if(depth > nod2.depth)
    {
        nod2.depth = depth;
        nod2.nod = nod;
    }
    for(i = 0; i < v[nod].size(); i++)
    {
        int vecin = v[nod][i];
        if(vecin != tata && viz[vecin] == 0)
        {
            dfs(vecin, nod, depth + 1);
        }
    }
}

int main()
{
    int n,a,b,i;
    f>>n;
    for(i = 1; i < n; i++)
    {
        f>>a>>b;
        v[a].push_back(b);
        v[b].push_back(a);
    }
    dfs(1, 0, 0);
    nod1.depth = nod2.depth;
    nod1.nod = nod2.nod;
    nod2.depth = 0;
    nod2.nod = 0;
    init(n);
    dfs(nod1.nod, 0 ,0);

    g<<nod2.depth + 1;
    return 0;
}