Cod sursa(job #1337659)

Utilizator shervladVlad Seremet shervlad Data 9 februarie 2015 12:26:11
Problema Diametrul unui arbore Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.18 kb
#include <iostream>
#include <fstream>
#include <list>
#include <vector>
#include <queue>
#include <mem.h>
#define NMAX 100005
using namespace std;

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

	int N;
	vector<list<int> > AdjList;
	list<int>::iterator it;
void Citire(){
	in>>N;
	AdjList.resize(N+1);
	int x,y;
		for(int i=1;i<N;i++){
			in>>x>>y;
			AdjList[x].push_back(y);
			AdjList[y].push_back(x);
		}
}
int LastElement(int Start,int &distance){
	queue<int> Q;

	bool Viz[NMAX]={false};
	int dist[NMAX];
	Q.push(Start);
	dist[Start]=0;

        while(!Q.empty()){
                int CurrentNode=Q.front();
                Q.pop();
                Viz[CurrentNode]=true;

                for(it=AdjList[CurrentNode].begin();it!=AdjList[CurrentNode].end();it++)
                    if(!Viz[*it]) {Q.push(*it); dist[*it]=dist[CurrentNode]+1;}

                if(Q.empty()){
                    distance=dist[CurrentNode];
                    return CurrentNode;
                }
        }
}
int main(){
	Citire();
	int diametru=0;
	int Capat1=LastElement(1,diametru);
	int Capat2=LastElement(Capat1,diametru);
	out<<diametru;
	return 0;
}