Cod sursa(job #2815405)

Utilizator pizzandreeaCiurescu Andreea pizzandreea Data 9 decembrie 2021 16:11:36
Problema Diametrul unui arbore Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.56 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
#include <algorithm>
#include <queue>

#define MAX 100001
#define INF 1000000001

using namespace std;

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


class Graf{


    public:
        int mN;
        int mM;
        vector<int> A[MAX];
        vector<bool> viz;


        int diametru;
        int start;

        Graf(int N, int M):mN(N), mM(M){}
        
        void CitireG();
        void DFSA(int s, int dist);
        void Diametru();

};

void Graf :: CitireG(){
    
    int x,y;

    for(int i = 1; i < mN; i++){
        fin >> x >> y;
        A[x].push_back(y);
        A[y].push_back(x);
    }

}

//dist - distanta de la nodul sursa la care am inceput dfs
// pana la nodul curent din dfs
void Graf :: DFSA(int s, int dist){
    viz[s] = 1;
     //fout << dist;
    if(dist > diametru){
        diametru = dist;
        start = s;
       
    }

    for(int i = 0; i < A[s].size(); i++){
        if(!viz[A[s][i]])
            DFSA(A[s][i], dist+1);
    }
}

void Graf :: Diametru(){
    
    viz.resize(mN+1,0);
    diametru = 0;
    DFSA(1, 0);
    
    for(int i = 1; i <= mN; i++)
        viz[i] = 0;
        
    //fout << " "<< viz[1] << " "<<viz[2];
        
    diametru = 0;
    //fout <<" "<< start;

    DFSA(start, 0);
    fout << diametru + 1;

}

int main(){
   int N, M;
    fin >> N;
    //fout << N;
    M = N-1;

    Graf G(N,M);
    G.CitireG();
    G.Diametru();



    return 0;
}