Cod sursa(job #2246512)

Utilizator AlexPascu007Pascu Ionut Alexandru AlexPascu007 Data 27 septembrie 2018 10:14:33
Problema Diametrul unui arbore Scor 90
Compilator cpp Status done
Runda Arhiva educationala Marime 0.98 kb
#include <fstream>
#include <vector>
#define DIM 100005
using namespace std;
ifstream fin("darb.in");
ofstream fout("darb.out");
int n,m,v[DIM],c[DIM],r,k,cc,i,j,cnt,l[DIM],maxim=0;
bool ok=false;
vector<int> L[DIM];
void bfs(int start, int componenta) {
    v[start]=componenta;
    c[1]=start;
    int p=1,u=1;
    while (p<=u) {
        int nod=c[p];
        for (i=0;i<L[nod].size();i++) {
            int vecin=L[nod][i];
            if (v[vecin]==0) {
                c[++u]=vecin;
                v[vecin]=componenta;
                l[vecin]=1+l[nod];
                if (l[vecin]>maxim) {
                    maxim=l[vecin];
                    r=vecin;
                }
            }
        }
        p++;
    }
}
int main() {
    fin>>n;
    for (k=1;k<n;k++) {
        fin>>i>>j;
        L[i].push_back(j);
        L[j].push_back(i);
    }
    bfs(1,1);
    for (i=1;i<=n;i++)
        l[i]=v[i]=0;
    i=r;
    bfs(i,1);
    fout<<1+l[r];
}