Pagini recente » Monitorul de evaluare | Cod sursa (job #244961) | Cod sursa (job #1455484) | Cod sursa (job #2373798) | Cod sursa (job #2814536)
#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;
}