Pagini recente » Cod sursa (job #2684894) | Cod sursa (job #2969323) | Cod sursa (job #1899062) | Cod sursa (job #192978) | Cod sursa (job #2814058)
#include <bits/stdc++.h>
#define NMax 100001
using namespace std;
ifstream fin("darb.in");
ofstream fout("darb.out");
class graf
{
int nrNoduri, nrMuchii;
bool orientat;
vector <int> gr[NMax]; // liste de adiacenta ale grafului
public:
graf(int n, int m, bool o); // constructor
void Citire_Arbore();
// Diametrul unui arbore
void Diametru_Arbore();
void BFS_Diametru_Arbore(int s, int &ultim, int &distanta_maxima);
};
int N, M;
graf :: graf(int n, int m, bool o)
{
nrNoduri = n;
nrMuchii = m;
orientat = o;
}
void graf :: Citire_Arbore()
{
for(int i = 1; i <= nrMuchii; ++i)
{
int x, y;
fin >> x >> y;
gr[x].push_back(y);
gr[y].push_back(x);
}
}
void graf :: BFS_Diametru_Arbore(int s, int &capat, int &distanta_maxima)
{
int distanta[NMax];
queue <int> q;
bool viz[NMax] = {0};
viz[s] = 1;
distanta[s] = 1;
q.push(s);
while(!q.empty())
{
int k = q.front();
q.pop();
for(auto i : gr[k])
if(!viz[i])
{
viz[i] = 1;
q.push(i);
distanta[i] = distanta[k] + 1;
}
}
distanta_maxima = 0;
for(int i = 1; i<= nrNoduri; ++i)
if(distanta[i] > distanta_maxima)
{
distanta_maxima = distanta[i];
capat = i;
}
}
void graf :: Diametru_Arbore()
{
int capat1, capat2, distanta_maxima;
BFS_Diametru_Arbore(1, capat1, distanta_maxima);
BFS_Diametru_Arbore(capat1, capat2, distanta_maxima);
fout << distanta_maxima;
}
int main()
{
fin >> N;
graf G(N, N-1, 0); // arbore
G.Citire_Arbore();
G.Diametru_Arbore();
return 0;
}