Pagini recente » Cod sursa (job #1108870) | Cod sursa (job #3268618) | Cod sursa (job #115808) | Cod sursa (job #2062813) | Cod sursa (job #2800892)
#include <bits/stdc++.h>
using namespace std;
ifstream f("darb.in");
ofstream g("darb.out");
const int NMAX=1e5+5;
int n, last, diametru, cnt[NMAX], dad[NMAX], finish;
vector<int> G[NMAX], res;
void bfs(int nod){
bool vis[NMAX]={0};
vis[nod]=1;
memset(cnt, 0, NMAX);
cnt[nod]=0;
queue<int> q;
q.push(nod);
while(!q.empty()){
int x=q.front();
q.pop();
for(auto i : G[x]){
if(!vis[i]){
q.push(i);
vis[i]=1;
cnt[i]=cnt[x]+1;
if(cnt[i] > diametru) {
diametru = cnt[i];
last = i;
}
}
}
}
}
void back(int nod){
bool vis[NMAX]={0};
memset(cnt, 0, NMAX);
vis[nod]=1;
queue<int> q;
q.push(nod);
diametru = 0;
while(!q.empty()){
int x=q.front();
q.pop();
for(auto i : G[x]){
if(!vis[i]){
vis[i] = 1;
cnt[i] = cnt[x] + 1;
dad[i] = x;
if(cnt[i] > diametru) {
diametru = cnt[i];
finish = i;
}
q.push(i);
}
}
}
}
int main(){
f >> n;
int k=n-1;
while(k--){
int x, y;
f >> x >> y;
G[x].push_back(y);
G[y].push_back(x);
}
bfs(1);
//cout << last << '\n';
back(last);
g << diametru + 1 << '\n';
//cout << finish << ' ';
// while(finish != 0) {
// res.push_back(finish);
// finish = dad[finish];
// }
// reverse(res.begin(), res.end());
// for(int i = 0; i < (int)res.size(); i++) {
// g << res[i] << ' ';
// }
return 0;
}