Pagini recente » Cod sursa (job #2508239) | Cod sursa (job #1391154) | Cod sursa (job #399588) | Cod sursa (job #1116650) | Cod sursa (job #2266123)
#include <iostream>
#include <queue>
#include <vector>
#include <fstream>
using namespace std;
struct Node{
int value;
int distanceFromSource;
};
int verticesNumber, edgeNumber;
vector<int> *adj;
void addEdge(int , int );
Node bfs(int );
int main(){
ifstream read("darb.in");
ofstream write("darb.out");
read>>verticesNumber;
adj = new vector<int>[verticesNumber];
edgeNumber = verticesNumber - 1;
for(int i=0; i<edgeNumber; i++)
{
int x, y;
read>>x>>y;
x--;
y--;
addEdge(x, y);
}
Node oneEnd = bfs(0);
Node anotherEnd = bfs(oneEnd.value);
write<<anotherEnd.distanceFromSource;
return 0;
}
Node bfs(int s){
bool *visited = new bool[verticesNumber];
for(int i=0; i<verticesNumber; i++)
visited[i] = false;
queue<Node> Q;
Node sourceNode;
sourceNode.value = s;
sourceNode.distanceFromSource = 1;
Q.push(sourceNode);
visited[s] = true;
int distance;
while(!Q.empty()){
sourceNode = Q.front();
distance = sourceNode.distanceFromSource;
Q.pop();
vector<int>::iterator it = adj[sourceNode.value].begin();
for(; it!=adj[sourceNode.value].end(); ++it){
if(!visited[(*it)]){
visited[(*it)] = true;
Node aux;
aux.value = (*it);
aux.distanceFromSource = sourceNode.distanceFromSource + 1;
Q.push(aux);
}
}
}
Node endNode;
endNode.value = sourceNode.value;
endNode.distanceFromSource = distance;
return endNode;
}
void addEdge(int v, int w){
adj[v].push_back(w);
adj[w].push_back(v);
}