Cod sursa(job #2531012)

Utilizator mirceatlxhaha haha mirceatlx Data 25 ianuarie 2020 16:05:12
Problema Diametrul unui arbore Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.07 kb
#include <iostream>
#include <fstream>
#include <queue>
#include <vector>
#include <cstring>
#define NMAX 100005
using namespace std;

ifstream fin("darb.in");
ofstream fout("darb.out");

vector <int> G[NMAX];
queue <int> q;
int N, steps[NMAX], last, diam;
bool viz[NMAX];

void BFS(int start)
{
    int act;
    memset(steps,0,sizeof(steps));
    memset(viz,false,sizeof(viz));
    q.push(start);
    steps[start] = 1;
    viz[start] = true;
    while(!q.empty()){
        act = q.front();
        for(int i = 0; i < G[act].size(); i++){
            if(!viz[G[act][i]]){
                q.push(G[act][i]);
                steps[G[act][i]] = steps[act] + 1;
                viz[G[act][i]] = true;
                diam = steps[G[act][i]];
                last = G[act][i];
            }
        }
        q.pop();
    }
}

int main()
{
    int x, y;
    fin >> N;
    for(int i = 1; i < N; i++){
        fin >> x >> y;
        G[x].push_back(y);
        G[y].push_back(x);
    }
    BFS(1);
    BFS(last);
    fout << diam << "\n";
    return 0;
}