Cod sursa(job #2458052)

Utilizator lucian2015blaugranadevil lucian2015 Data 19 septembrie 2019 14:34:21
Problema Diametrul unui arbore Scor 90
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.82 kb
#include <fstream>
#include <vector>
#include <queue>
#include <bits/stdc++.h>
#define inf 1000001
#define BUFFER_SIZE 270000
using namespace std;

#define BUFFER_SIZE 270000

 
 __attribute__((always_inline)) int get_int()		
{
    static char inBuffer[BUFFER_SIZE];
    static int p = BUFFER_SIZE - 1; int number = 0;
    for(; inBuffer[p] < 47;)
    {
	
        ++p != BUFFER_SIZE || (fread(inBuffer, 1, BUFFER_SIZE, stdin), p = 0);
    }
    for(; inBuffer[p] > 47;)
    {
	
        number = number * 10 + inBuffer[p] - 48;
        ++p != BUFFER_SIZE || (fread(inBuffer, 1, BUFFER_SIZE, stdin), p = 0);
    }	
    return number;	
}
	

class arbre{
private:
	vector< int > *edges;
	int nodes = 0;
	int llast;
public:
	arbre( int n ){
		edges = new vector<int>[n + 1];
		nodes = n;
	}
	void addedge( int x, int y ){
		edges[x].push_back(y);
		edges[y].push_back(x);
	}
	int bfs( int source ){
		queue<int> coada;
		vector<int> dist(nodes, inf);
		int last;
		vector<bool> visited(nodes, 0);
		coada.push(source);
		visited[source] = 1;
		dist[source] = 1;
		while( !coada.empty() ){
			int nod = coada.front();
			coada.pop();
			for ( int i = 0; i < edges[nod].size(); i++){
				if( visited[edges[nod][i]] == 0){
					visited[edges[nod][i]] = 1;
					dist[edges[nod][i]] = dist[nod] + 1;
					coada.push(edges[nod][i]);
				}
			}

		}
		int maxi = dist[ source ];
		for ( int i = 1; i <= nodes; i++ ){
			if( maxi < dist[i] ){
				maxi = dist[i];
				last = i;
			}
		}
		llast = last;
		return maxi;

	}
	int getlast(){
		return llast;
	}
};



int main(){
freopen("darb.in", "r", stdin);	
freopen("darb.out", "w", stdout);
 int n, x, y;
 n = get_int();
 arbre arbore(n);
 for ( int i = 1; i <= n - 1; i++ ){
 	x = get_int();
 	y = get_int();
 	arbore.addedge(x, y);
 	arbore.addedge(x, y);
 }
 arbore.bfs(1);
 printf("%d",arbore.bfs(arbore.getlast()));

}