Cod sursa(job #2814536)

Utilizator Angel2IonitaAngel Ionita Angel2Ionita Data 8 decembrie 2021 11:41:20
Problema Diametrul unui arbore Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.46 kb
#include <vector>
#include <fstream>

using namespace std;

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

class Graph
{
    int fnode;
    vector<vector<int>> adjList;
    void dfs_base(int node, int k, bool visited[], int &diameter)
    {
        visited[node] = true;
        k++;
        for (auto i : adjList[node])
        {
            if (!visited[i])
            {
                if (k >= diameter)
                {
                    diameter = k;
                    fnode = i;
                }
                dfs_base(i, k, visited, diameter);
            }
        }
    }
    void dfs_darb(int node, int &diameter)
    {
        bool *visited = new bool[size];
        int k = 0;
        for (int i = 0; i < size; i++)
            visited[i] = false;
        dfs_base(node, k + 1, visited, diameter);
    }

public:
    int size;
    Graph(int n)
    {
        size = n;
        adjList.resize(size);
    }
    void addEdgeUndirected(int start, int end)
    {
        adjList[start].push_back(end);
        adjList[end].push_back(start);
    }
    int diameter()
    {
        int diameter = -1;
        dfs_darb(0, diameter);
        dfs_darb(fnode, diameter);
        return diameter;
    }
};

int main()
{
    int N, x, y;
    f >> N;
    Graph g(N);
    for (int i = 1; i <= N - 1; i++)
    {
        f >> x >> y;
        g.addEdgeUndirected(x - 1, y - 1);
    }
    o << g.diameter();
    return 0;
}