Cod sursa(job #2814538)

Utilizator atudoreimirunaAtudorei Miruna Gabriela atudoreimiruna Data 8 decembrie 2021 11:42:02
Problema Diametrul unui arbore Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.69 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>

#define Max 100001

using namespace std;

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

int N, M;

class Graph{
private:
    int NumberOfNodes, NumberOfEdges;
    vector<int> adjacencyList[Max];
    
public:
    Graph(int N, int M); // constructor
    void Read_UndirectedGraph();
    void BFS_Darb(int Start_node, int &max_diameter, int &next_node);
    void Darb();
};

// constructor
Graph :: Graph(int N, int M)
{
    NumberOfNodes = N;
    NumberOfEdges = M;
}

void Graph :: Read_UndirectedGraph()
{
    for ( int i = 1; i <= NumberOfEdges; i++ )
    {
        int x, y;
        fin >> x >> y;
        adjacencyList[x].push_back(y);
        adjacencyList[y].push_back(x);
    }
}

void Graph :: BFS_Darb(int Start_node, int &max_diameter, int &next_node)
{
    int d[Max];
    bool visited[Max] = {0};
    queue<int> q;
    
    visited[Start_node] = 1;
    q.push(Start_node);
    d[Start_node] = 1;

    while ( !q.empty() )
    {
        int node = q.front();
        for ( auto i : adjacencyList[node] )
            if ( !visited[i] )
            {
                visited[i] = 1;
                q.push(i);
                d[i] = d[node] + 1;
            }
        q.pop();
    }

    max_diameter = 0;
    for ( int i = 1; i <= NumberOfNodes; i++ )
        if ( d[i] > max_diameter )
        {
            max_diameter = d[i];
            next_node = i;
        }
}

void Graph :: Darb()
{
    int first, next, max_diameter;
    BFS_Darb(1, first, max_diameter);
    BFS_Darb(first, next, max_diameter);
    fout << max_diameter;
}

int main()
{
    fin >> N;
    Graph G(N,N-1);
    G.Read_UndirectedGraph();
    G.Darb();

    return 0;
}