Pagini recente » Cod sursa (job #355633) | Cod sursa (job #2100558) | Cod sursa (job #1114930) | Cod sursa (job #2300425) | Cod sursa (job #2685852)
#include <bits/stdc++.h>
#define MAX 100100
using namespace std;
fstream in("darb.in");
ofstream out("darb.out");
vector<int> Graph[MAX];
int N;
int cost[MAX];
int S[MAX];
void BFS(int nod, int &finish) {
memset(cost, -1, sizeof(cost)); //Set all the costs to -1
int L = 1;
S[L] = nod; //Add the node to the queue
cost[nod] = 0; //Cost to same node is 0
for(int i = 1; i <= L; i++) //While queue is not empty
for(int j = 0; j < Graph[S[i]].size(); j++) // Check the neighbours
if(cost[Graph[S[i]][j]] == -1) { //If not visited already
S[++L] = Graph[S[i]][j]; //Add to queue
finish = Graph[S[i]][j];
cost[S[L]] = cost[S[i]] + 1; //Increase cost of neighbour
}
}
int main() {
in >> N;
int x, y, finish,ans;
for(int i = 1; i < N; i++) {
in >> x >> y;
Graph[x].push_back(y);
Graph[y].push_back(x);
}
BFS(1, finish); //BFS din nod oarecare, retin ultimul nod unde ajung
BFS(finish,y); //BFS din ultimul nod ajuns, gasesc celalalt capat al lantului
out<<cost[y]+1;
return 0;
}