Cod sursa(job #2066751)

Utilizator Andrei2000Andrei Mihailescu Andrei2000 Data 15 noiembrie 2017 13:57:07
Problema Diametrul unui arbore Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.01 kb
#include <bits/stdc++.h>
#define nmax 100002

using namespace std;

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

vector<int> G[nmax];
const int inf=0x3f3f3f3f;
int n,v[nmax];

void read(){
    int a,b;
    fin>>n;
    for(int i=1;i<n;++i){
        fin>>a>>b;
        G[a].push_back(b);
        G[b].push_back(a);
    }
}

int bfs_max(int node,int &maxn,int &maxpos){
    maxn=0;
    maxpos=node;
    queue <int> Q;
    Q.push(node);
    memset(v,inf,sizeof(v));
    v[node]=1;
    while(!Q.empty()){
        int node1=Q.front();
        Q.pop();
        for(auto node2: G[node1])
            if(v[node2]==inf){
                v[node2]=v[node1]+1;
                maxn=max(maxn,v[node2]);
                if(v[node2]==maxn)maxpos=node2;
                Q.push(node2);
            }
    }
}

int diameter(){
    int node1,node2,dist;
    bfs_max(1,dist,node1);
    bfs_max(node1,dist,node2);
    return dist;
}

int main()
{
    read();
    fout<<diameter();
    return 0;
}