Cod sursa(job #2685852)

Utilizator RNedelcuNedelcu Radu RNedelcu Data 17 decembrie 2020 20:34:13
Problema Diametrul unui arbore Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.14 kb
#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;
}