Cod sursa(job #2569005)

Utilizator mihai50000Mihai-Cristian Popescu mihai50000 Data 4 martie 2020 10:46:42
Problema Diametrul unui arbore Scor 100
Compilator cpp-64 Status done
Runda r3capitusulare Marime 0.86 kb
#include <bits/stdc++.h>

using namespace std;

ifstream fin("darb.in");
ofstream fout("darb.out");

const int DIM = 1e5 + 1;

vector <int> adj[DIM];
bitset <DIM> vis;
int dist[DIM];

main()
{
	int n;
	fin >> n;
	
	for(int i = 1; i < n; ++i)
	{
		int x, y;
		fin >> x >> y;
		
		adj[x].emplace_back(y);
		adj[y].emplace_back(x);
	}
	
	queue <int> q;
	q.emplace(1);
	
	int last = 1;
	
	while(!q.empty())
	{
		int nod = q.front();
		q.pop();
		
		last = nod;
		
		for(auto i : adj[nod])
			if(vis[i] == false)
			{
				q.emplace(i);
				vis[i] = true;
			}
	}
	
	q.emplace(last);
	vis[last] = false;
	
	int ans = 1;
	dist[last] = 1;
	
	while(!q.empty())
	{
		int nod = q.front();
		q.pop();
		
		ans = max(ans, dist[nod]);
		
		for(auto i : adj[nod])
			if(vis[i] == true)
			{
				vis[i] = false;
				q.emplace(i);
				dist[i] = dist[nod] + 1;
			}
	}
	
	fout << ans << '\n';
}