Pagini recente » Cod sursa (job #601090) | Cod sursa (job #846497) | Cod sursa (job #2917276) | Cod sursa (job #645678) | Cod sursa (job #2786673)
#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;
}