Cod sursa(job #2560966)

Utilizator richardbaczur1Baczur Richard richardbaczur1 Data 28 februarie 2020 13:44:48
Problema Diametrul unui arbore Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.33 kb
#include <bits/stdc++.h>
#define NMAX 100005
#define infile "darb.in"
#define outfile "darb.out"

using namespace std;

struct node
{
    vector<int> adj;
};
vector<node> v;
int n, x, y;

pair<int, int> find_first_node(int root)
{
    int max_depth = 0, best_node;
    queue< pair<int, int> > q;
    bitset<NMAX> viz;
    q.push(make_pair(root, 1));
    viz[root] = 1;
    while (!q.empty())
    {
        int nod = q.front().first;
        int depth = q.front().second;
        q.pop();
        for (unsigned int i = 0; i < v[nod].adj.size(); i++)
        {
            if (!viz[v[nod].adj[i]])
            {
                viz[v[nod].adj[i]] = 1;
                q.push(make_pair(v[nod].adj[i], depth + 1));
            }
        }
        if (depth > max_depth)
        {
            max_depth = depth;
            best_node = nod;
        }
    }
    return make_pair(best_node, max_depth);
}

int main()
{
    freopen(infile, "r", stdin);
    freopen(outfile, "w", stdout);

    scanf("%d", &n);
    v.resize(n + 3);
    for (int i = 1; i < n; i++)
    {
        scanf("%d %d", &x, &y);
        v[x].adj.push_back(y);
        v[y].adj.push_back(x);
    }
    int st = find_first_node(1).first;
    printf("%d", find_first_node(st).second);

    fclose(stdin);
    fclose(stdout);
    return 0;
}