Pagini recente » Cod sursa (job #1098935) | Cod sursa (job #1651113) | Cod sursa (job #1505690) | Cod sursa (job #1168197) | Cod sursa (job #3123891)
#include <cstdio>
#include <vector>
#include <cstring>
using namespace std;
FILE *fin, *fout;
const int NMAX = 1e5;
vector <int> graph[NMAX + 5];
int n, dist[NMAX + 5], maxim, node_max1, node_max2;
bool viz[NMAX + 5];
void dfs1(int node)
{
if(dist[node] > maxim)
{
maxim = dist[node];
node_max1 = node;
}
viz[node] = 1;
for(int i = 0; i < graph[node].size(); i++)
{
int neigh = graph[node][i];
if(viz[neigh] == 0)
{
dist[neigh] = dist[node] + 1;
dfs1(neigh);
}
}
}
void dfs2(int node)
{
if(dist[node] > maxim)
{
maxim = dist[node];
node_max2 = node;
}
viz[node] = 1;
for(int i = 0; i < graph[node].size(); i++)
{
int neigh = graph[node][i];
if(viz[neigh] == 0)
{
dist[neigh] = dist[node] + 1;
dfs2(neigh);
}
}
}
int get_capete()
{
dfs1(1);
memset(viz, 0, sizeof viz);
memset(dist, 0, sizeof dist);
maxim = 0;
dfs2(node_max1);
return maxim;
}
int cnt, ans[NMAX + 5];
int main()
{
fin = fopen("darb.in", "r");
fout = fopen("darb.out", "w");
int n;
fscanf(fin, "%d", &n);
for(int i = 1; i <= n - 1; i++)
{
int u, v;
fscanf(fin, "%d%d", &u, &v);
graph[u].push_back(v);
graph[v].push_back(u);
}
fprintf(fout, "%d", get_capete() + 1);
fclose(fin);
fclose(fout);
return 0;
}