Pagini recente » Cod sursa (job #1546738) | Cod sursa (job #491271) | Cod sursa (job #847843) | Cod sursa (job #1550895) | Cod sursa (job #2812848)
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <stack>
#include <algorithm>
#define MAX 100001
using namespace std;
ifstream indarb("darb.in");
ofstream outdarb("darb.out");
class Graf
{
int NrNoduri;
public:
vector<int> Adiacenta[MAX];
Graf(int NrNoduri);
void AdaugaMuchie(int nod, int nodConectat);
void AdaugaMUchieNeorientat(int nod, int nodConectat);
void Bfsdarb(int nod, int *nodinitial, int *nodfinal);
};
//ADAUGARE MUCHII
Graf::Graf(int NrNoduri)
{
this->NrNoduri = NrNoduri;
}
void Graf::AdaugaMuchie(int nod, int nodConectat)
{
Adiacenta[nod].push_back(nodConectat);
}
void Graf::AdaugaMUchieNeorientat(int nod, int nodConectat)
{
Adiacenta[nod].push_back(nodConectat);
Adiacenta[nodConectat].push_back(nod);
}
void Graf::Bfsdarb(int nod, int* nodinit, int *dist)
{
int distanta[NrNoduri] = {0};
distanta[nod] = 1;
queue<int> Q;
bool Vizitat[NrNoduri] = {0};
Q.push(nod);
Vizitat[nod] = 1;
while(!Q.empty())
{
nod = Q.front();
Q.pop();
for(auto i: Adiacenta[nod])
{
if(!Vizitat[i])
{
Q.push(i);
Vizitat[i] = 1;
distanta[i] = distanta[nod] + 1;
}
}
}
int distMax = -1;
int nodinitial;
for(int i = 1; i < NrNoduri; i++)
if(distanta[i] > distMax)
{
distMax = distanta[i];
nodinitial = i;
}
*nodinit = nodinitial;
*dist = distMax;
}
int main()
{
int NrNoduri;
indarb >> NrNoduri;
Graf g(NrNoduri+1);
int a, b;
for(int i = 0; i < NrNoduri; i++)
{
indarb >> a >> b;
g.AdaugaMUchieNeorientat(a, b);
}
int nodinit, dist;
g.Bfsdarb(1, &nodinit, &dist);
g.Bfsdarb(nodinit, &nodinit, &dist);
outdarb << dist;
return 0;
}