Cod sursa(job #2458055)

Utilizator lucian2015blaugranadevil lucian2015 Data 19 septembrie 2019 14:42:10
Problema Diametrul unui arbore Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.25 kb
#include <fstream>
#include <vector>
#include <queue>
#define inf 1000001

using namespace std;

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

class arbre{
private:
	vector< int > *edges;
	int nodes = 0;
	int llast = 0;
public:
	arbre( int n ){
		edges = new vector<int>[n + 100];
		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+100, inf);
		int last;
		vector<bool> visited(nodes+100, 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(){
 int n, x, y;
 f >> n;
 arbre arbore(n);
 for ( int i = 1; i <= n - 1; i++ ){
 	f >> x >> y;
 	arbore.addedge(x, y);
 	arbore.addedge(x, y);
 }
 arbore.bfs(1);
 g << arbore.bfs(arbore.getlast());


}