Mai intai trebuie sa te autentifici.
Cod sursa(job #1691191)
Utilizator | Data | 17 aprilie 2016 11:02:44 | |
---|---|---|---|
Problema | Diametrul unui arbore | Scor | 100 |
Compilator | cpp | Status | done |
Runda | Arhiva educationala | Marime | 0.91 kb |
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
using namespace std;
vector <vector <int> > graph;
vector <int> visited;
int n, dim;
ifstream f("darb.in");
ofstream g("darb.out");
int bfs(int vertex)
{
queue <int> q;
int element, i;
q.push(vertex);
visited[vertex] = true;
while (!q.empty())
{
element = q.front();
for (i = 0; i < graph[element].size(); i++)
if (visited[graph[element][i]]==-1)
{
q.push(graph[element][i]);
visited[graph[element][i]] = visited[element]+1;
}
q.pop();
}
dim=visited[element];
return element;
}
int main()
{
int i,x,y;
f >> n;
graph.resize(n);
visited.resize(n, -1);
for (i = 0; i < n - 1; i++)
{
f >> x >> y;
x--;
y--;
graph[x].push_back(y);
graph[y].push_back(x);
}
x = bfs(0);
visited.clear();
visited.resize(n, -1);
y = bfs(x);
g<<dim;
return 0;
}