Cod sursa(job #2500372)

Utilizator YetoAdrian Tonica Yeto Data 27 noiembrie 2019 19:48:39
Problema Diametrul unui arbore Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.91 kb
#include <fstream>
#include <cstring>
#include <vector>
#include <queue>
using namespace std;
int n, i, j, x, y, darb;
int d[100001];
bool viz[100001];
vector <int> g[100001];
queue <int> q;
ifstream fin ("darb.in");
ofstream fout ("darb.out");

void bfs (int s)
{
    int x=0;
    memset(viz, 0, sizeof(viz));
    memset(d, 0, sizeof(d));
    viz[s]=1;
    q.push(s);
    while (!q.empty()) {
        x=q.front();
        q.pop();
        for (int i=0;i<g[x].size();i++) {
            int nod = g[x][i];
            if (!viz[nod]) {
                viz[nod]=1;
                d[nod]=d[x]+1;
                if (d[nod]>darb)
                    darb=d[nod];
                q.push(nod);
            }
        }
    }
}

int main () {
    fin>>n;
    for (i=1;i<n;i++) {
        fin>>x>>y;
        g[x].push_back(y);
        g[y].push_back(x);
    }
    for (i=1;i<=n;i++) {
        bfs(i);
    }
    fout<<darb+1;
    return 0;
}