Pagini recente » Cod sursa (job #2920025) | Cod sursa (job #3286613) | Cod sursa (job #3278033) | Cod sursa (job #3193201) | Cod sursa (job #1228362)
#include <fstream>
#include <iostream>
#include <vector>
#include <iterator>
#include <cstring>
#define MAXN 100002
using namespace std;
typedef vector<vector<int>> Graph;
Graph graph;
bool visited[MAXN];
int dfs(int node)
{
int dist = 0;
visited[node] = true;
for (int neighbor : graph[node])
{
if (visited[neighbor] == false)
{
dist = max(dist, dfs(neighbor));
}
}
return dist + 1;
}
void findFurthestNode(int node, int dist, int & furthest)
{
static int furthestDist = 0;
bool hasNeighbors = false;
//cout << "At " << node + 1 << endl;
visited[node] = true;
for (int neighbor : graph[node])
{
if (visited[neighbor] == false)
{
hasNeighbors = true;
findFurthestNode(neighbor, dist + 1, furthest);
}
}
if (hasNeighbors == false && dist > furthestDist)
{
//cout << node + 1 << " " << dist << endl;
furthestDist = dist;
furthest = node;
}
}
int main()
{
int n;
fstream fin("darb.in", fstream::in);
fstream fout("darb.out", fstream::out);
fin >> n;
//cout << n << endl;
graph.resize(MAXN);
for (int i=0; i<n-1; ++i)
{
int x, y;
fin >> x >> y;
//cout << x << " " << y << endl;
graph[x-1].push_back(y-1);
graph[y-1].push_back(x-1);
}
/*for (int i=0; i<n; ++i)
{
cout << i+1 << " ---> ";
for (int node : graph[i])
{
cout << node+1 << " ";
}
cout << endl;
}*/
int root = 0;
int dist = 0;
visited[0] = true;
findFurthestNode(0, 0, root);
//cout << root + 1 << endl;
memset(visited, 0, sizeof(visited));
dist = 0;
visited[root] = true;
for (int node : graph[root])
{
dist = max(dist, dfs(node));
}
fout << dist + 1 << endl;
return 0;
}