Cod sursa(job #2449150)

Utilizator red_devil99Mancunian Red red_devil99 Data 18 august 2019 13:31:42
Problema Diametrul unui arbore Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.76 kb
#include <bits/stdc++.h>
using namespace std;
ifstream fin("darb.in");
ofstream fout("darb.out");
#define maxn 100010
std::vector<int> v[maxn];
int verif[maxn];
int cost[maxn];
int last, N, diam;
queue<int> q;

void bfs(int nod){
    for(int i = 1; i <= N; i++){
		cost[i] = 0;
		verif[i] = 0;
	}
	cost[nod] = 0;
	verif[nod] = 1;
	q.push(nod);
	while(!q.empty()){
		int x = q.front();
		q.pop();
		for(int i = 0; i < v[x].size(); i++){
			if(!verif[v[x][i]]){
				verif[v[x][i]] = 1;
				cost[v[x][i]] = cost[x] + 1;
				diam = cost[v[x][i]];
				q.push(v[x][i]);
				last = v[x][i];
			}
		}
	}
}

int main(){
	fin >> N;
	for(int i = 1; i <= N-1; i++){
		int x, y;
		fin >> x >> y;
		v[x].push_back(y);
		v[y].push_back(x);
	}
	bfs(1);
	bfs(last);
	fout << diam+1;
	return 0;
}