Cod sursa(job #3361224)

Utilizator EricDimiCismaru Eric-Dimitrie EricDimi Data 22 iulie 2026 06:13:16
Problema Diametrul unui arbore Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.28 kb
#include <fstream>
#include <vector>
#include <bitset>
#include <queue>

using namespace std;

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

const int MAX_N = 100000;

vector<int> adj[MAX_N + 1];
bitset<MAX_N + 1> vis;
int diam, node1, node2;
int n;

struct State
{
    int node, dist;
};

inline int max(int x, int y)
{
    return (x > y) ? x : y;
}

inline void maxSelf(int& x, int y)
{
    x = (x > y) ? x : y;
}

void Read()
{
    f >> n;
    for(int i = 1; i < n; i++)
    {
        int x, y;
        f >> x >> y;
        adj[x].push_back(y);
        adj[y].push_back(x);
    }
}

void BFS(int source, bool id, int& dest)
{
    vis[source] = id;

    queue<State> q;
    q.push({source, 0});

    while(!q.empty())
    {
        State state = q.front();
        q.pop();

        for(int node : adj[state.node])
            if(vis[node] != id)
            {
                vis[node] = id;
                q.push({node, 1 + state.dist});
            }

        if(q.empty())
        {
            diam = state.dist;
            dest = state.node;
        }
    }
}

int main()
{
    Read();
    BFS(1, true, node1);
    BFS(node1, false, node2);
    g << (diam + 1) << '\n';

    f.close();
    g.close();

    return 0;
}