Cod sursa(job #1111381)

Utilizator BeilandArnoldArnold Beiland BeilandArnold Data 18 februarie 2014 20:37:38
Problema Diametrul unui arbore Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.93 kb
#include <fstream>
#include <vector>
#include <list>
#include <queue>



int main(){
	std::ifstream fin("darb.in");
	std::ofstream fout("darb.out");

	int n; fin>>n;
	std::vector< std::list<int> > Adj(n+1);

	for(int i=0;i<n;++i){
		int a,b; fin>>a>>b;
		Adj[a].push_back(b); Adj[b].push_back(a);
	}

	std::queue<int> q;
	std::vector<int> dist(n+1,-1);

	q.push(1); dist[1]=0;
	int m=0,mn=1;

	while(!q.empty()){
		for(auto it=Adj[q.front()].begin();it!=Adj[q.front()].end();++it){
			if(dist[*it]==-1){
				dist[*it]=dist[q.front()]+1;
				if(dist[*it]>m){
					m=dist[*it]; mn=*it;
				}
				q.push(*it);
			}
		}
		q.pop();
	}

	dist=std::vector<int>(n+1,-1);
	q.push(mn); dist[mn]=0;

	m=0;
	while(!q.empty()){
		for(auto it=Adj[q.front()].begin();it!=Adj[q.front()].end();++it){
			if(dist[*it]==-1){
				dist[*it]=dist[q.front()]+1;
				if(dist[*it]>m){
					m=dist[*it]; mn=*it;
				}
				q.push(*it);
			}
		}
		q.pop();
	}

	fout<<m+1<<'\n';
}