Pagini recente » Profil FlorinHaja | Cod sursa (job #2004074) | Cod sursa (job #679540) | Cod sursa (job #175033) | Cod sursa (job #1658047)
/*
* =====================================================================================
*
* Filename: diameter.cpp
*
* Description: http://www.infoarena.ro/problema/darb
*
* Version: 1.0
* Created: 03/20/2016 23:39:15
* Revision: none
* Compiler: gcc/g++
*
* Author: Marius-Constantin Melemciuc
* email:
* Organization:
*
* =====================================================================================
*/
#include <iostream>
#include <stack>
#include <queue>
#include <vector>
#include <fstream>
#include <cstdlib>
#include <ctime>
using namespace std;
vector<vector<int> > graph;
vector<bool> visited;
vector<int> visited2;
int getALeaf(int vertex, int n) {
if (vertex < 0 || vertex > n - 1) {
return 0;
}
queue<int> q;
int element, leafNode = vertex;
q.push(vertex);
visited[vertex] = true;
while (!q.empty()) {
element = q.front();
for (int i = 0; i < graph[element].size(); i++) {
if (!visited[graph[element][i]]) {
q.push(graph[element][i]);
visited[graph[element][i]] = true;
leafNode = graph[element][i];
}
}
q.pop();
}
return leafNode + 1;
}
int getBiggestDistance(int vertex, int n) {
if (vertex < 0 || vertex > n - 1) {
return 0;
}
queue<int> q;
int element;
q.push(vertex);
visited2[vertex] = 0;
while (!q.empty()) {
element = q.front();
for (int i = 0; i < graph[element].size(); i++) {
if (visited2[graph[element][i]] == -1) {
q.push(graph[element][i]);
visited2[graph[element][i]] = visited2[element] + 1;
}
}
q.pop();
}
int maxDistance = 0;
for (auto it = visited2.begin(); it != visited2.end(); it++) {
if (*it > maxDistance) {
maxDistance = (*it);
}
}
return maxDistance;
}
int getDiameter(int n) {
srand(time(NULL));
int randomNode = rand() % n;
int leafOne = getALeaf(randomNode, n);
int diameter = getBiggestDistance(leafOne - 1, n);
return diameter + 1;
}
int main() {
ifstream in("darb.in");
ofstream out("darb.out");
int n, m;
in >> n;
m = n - 1;
graph.resize(n);
visited.resize(n, false);
visited2.resize(n, -1);
int x, y;
for (int i = 0; i < m; i++) {
in >> x >> y;
x--;
y--;
graph[x].push_back(y);
graph[y].push_back(x);
}
out << getDiameter(n);
return 0;
}