Cod sursa(job #2786673)

Utilizator qubitrubbitQubit Rubbit qubitrubbit Data 21 octombrie 2021 14:45:47
Problema Diametrul unui arbore Scor 90
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.97 kb
#include <fstream>
#include <vector>
#include <queue>
#include <bits/stdc++.h>
using namespace std;

ifstream fin("darb.in");
ofstream fout("darb.out");

class Graph
{
private:
    int cntNodes;
    vector<vector<int>> adjList;

public:
    Graph(int n)
    {
        cntNodes = n;
        for (int i = 0; i < n; ++i)
        {
            adjList.push_back(vector<int>());
        }
    }

    void addEdge(int from, int to, bool oriented)
    {
        adjList[from].push_back(to);
        if (!oriented)
        {
            adjList[to].push_back(from);
        }
    }

    pair<int, int> maxBfsDist(int source)
    {
        bool visited[cntNodes];
        fill(visited, visited + cntNodes, false);
        visited[source] = true;

        int dist[cntNodes];
        fill(dist, dist + cntNodes, -1);
        dist[source] = 0;

        queue<int> q;
        q.push(source);
        while (!q.empty())
        {
            int top = q.front();
            q.pop();
            for (int childId : adjList[top])
            {
                if (!visited[childId])
                {
                    dist[childId] = dist[top] + 1;
                    visited[childId] = true;
                    q.push(childId);
                }
            }
        }
        int maxDist = 0;
        int nodeId = -1;
        for (int i = 0; i < cntNodes; ++i)
        {
            if (maxDist < dist[i])
            {
                maxDist = dist[i];
                nodeId = i;
            }
        }
        return {nodeId, maxDist};
    }

    int getTreeDiameter()
    {
        pair<int, int> s = maxBfsDist(0);
        pair<int, int> d = maxBfsDist(s.first);
        return d.second + 1;
    }
};

int n, m, a, b, s;
int main()
{
    fin >> n;
    Graph g(n);
    for (int i = 0; i < n - 1; ++i)
    {
        fin >> a >> b;
        g.addEdge(a - 1, b - 1, false);
    }
    fout << g.getTreeDiameter();
    return 0;
}