Pagini recente » Cod sursa (job #667526) | Cod sursa (job #1264104) | Cod sursa (job #2502952) | Cod sursa (job #2277954) | Cod sursa (job #2814538)
#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;
}