Pagini recente » Cod sursa (job #2801694) | Cod sursa (job #1540934) | Cod sursa (job #1788699) | Cod sursa (job #729569) | Cod sursa (job #1958058)
#include <iostream>
#include <fstream>
#include <cstring>
#include <stdlib.h>
#include <stdio.h>
#include <math.h>
#include <vector>
#include <stack>
#include <list>
#include <algorithm>
#include <limits.h>
#include <queue>
#include <utility>
#include <set>
using namespace std;
//longest chain in a tree
ifstream f("darb.in");
ofstream g("darb.out");
int n, m;
vector<int> tree[100001];
pair<int, int> BFSdistances (int root);
int longestChain(int root){
pair<int, int> res1 = BFSdistances(root);
//cout << res1.first << " " << res1.second << endl;
pair<int, int> res2 = BFSdistances(res1.first);
//cout << res2.first << " " << res2.second << endl;
return res2.second + 1; // we include the start node aswell
}
pair<int, int> BFSdistances (int root){
int maxDistance = -1;
int maxDistanceNode;
queue<pair<int, int> > q;
set<int> visited;
q.push(pair<int, int> (root,0));
while (!(q.empty())){
pair<int, int> inter = q.front();
q.pop();
visited.insert(inter.first);
if(inter.second > maxDistance){
maxDistance = inter.second;
maxDistanceNode = inter.first;
}
//cout << inter.first << " " << inter.second << endl;
for(int node: tree[inter.first]){
if(visited.find(node) == visited.end())
q.push(pair<int, int> (node, inter.second + 1));
}
}
return pair<int, int>(maxDistanceNode, maxDistance);
}
int main(){
f >> n;
m = n - 1;
for(int i = 0; i < m; i++){
int from, to;
f >> from >> to;
tree[from].push_back(to);
tree[to].push_back(from);
}
g << longestChain(1) << endl;
return 0;
}