Cod sursa(job #2137076)

Utilizator catalinlupCatalin Lupau catalinlup Data 20 februarie 2018 16:23:52
Problema Diametrul unui arbore Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.15 kb
#include <bits/stdc++.h>
#define INFILE "darb.in"
#define OUTFILE "darb.out"
using namespace std;
ifstream in(INFILE);
ofstream out(OUTFILE);
int N;
struct Graph{
    int n;
    vector<vector<int>> Adj;
    void init(int n){
        this->n=n;
        Adj.resize(n+1);
    }
    void Add(int x,int y){
        Adj[x].push_back(y);
    }
}G;

void Read(){
    in>>N;
    G.init(N);
    for(int i=1;i<=N-1;i++){
        int x,y;
        in>>x>>y;
        G.Add(x,y);
        G.Add(y,x);
    }
}
void dfsUtil(int x,int Count,int &maxDist,int &maxNod,bool viz[]){
    viz[x]=true;
    if(Count>maxDist){
        maxDist=Count;
        maxNod=x;
    }
    for(auto y:G.Adj[x]){
        if(viz[y]) continue;
        dfsUtil(y,Count+1,maxDist,maxNod,viz);
    }
}
void DFS(int x,int &maxDist,int &maxNod){
    bool viz[N+1];
    memset(viz,0,sizeof(viz));
    maxDist=0;
    maxNod=x;
    dfsUtil(x,0,maxDist,maxNod,viz);
}
int Diametru(){
    int mxdst;
    int mxnod;
    DFS(1,mxdst,mxnod);
    int nod2;
    DFS(mxnod,mxdst,nod2);
    return mxdst+1;
}
int main()
{
    Read();
    out<<Diametru();
    return 0;
}