Pagini recente » Cod sursa (job #3147590) | Cod sursa (job #2407167) | Cod sursa (job #2433734) | Cod sursa (job #3287096) | Cod sursa (job #2815405)
#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;
}