Pagini recente » Cod sursa (job #1588550) | Cod sursa (job #1000417) | Cod sursa (job #2539294) | Cod sursa (job #2618552) | Cod sursa (job #2814242)
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
using namespace std;
ifstream fin("darb.in");
ofstream fout("darb.out");
class Graf
{
int numar_noduri;
vector <int> lista_adiacenta[100];
public:
void citire();
void bfs_darb(int, int&, int&);
void bfs_darb_init();
};
void Graf :: citire()
{
int capat_stang, capat_drept;
fin >> numar_noduri;
for(int i = 0; i <= numar_noduri; i++)
{
lista_adiacenta[i].push_back(-1);
}
for(int i = 0; i < numar_noduri; i++)
{
fin >> capat_stang >> capat_drept;
lista_adiacenta[capat_stang].push_back(capat_drept);
lista_adiacenta[capat_drept].push_back(capat_drept);
}
}
void Graf :: bfs_darb_init()
{
int distanta, nod1, nod2;
bfs_darb(1, nod1, distanta);
bfs_darb(nod1, nod2, distanta);
fout << distanta;
}
void Graf :: bfs_darb(const int s, int &u, int &d)
{
int a;
int vizitat[numar_noduri + 1] = {};
int dist[numar_noduri + 1] = {};
queue <int> coada;
d = 0;
dist[s] = 1;
vizitat[s] = 1;
coada.push(s);
while(!coada.empty())
{
a = coada.front();
coada.pop();
for(int i = 1; i < lista_adiacenta[a].size(); i++)
if(vizitat[lista_adiacenta[a][i]] == 0)
{
vizitat[lista_adiacenta[a][i]] = 1;
coada.push(lista_adiacenta[a][i]);
dist[lista_adiacenta[a][i]] = dist[a] + 1;
}
}
for(int i = 1; i <= numar_noduri; i++)
if(d < dist[i])
{
d = dist[i];
u = i;
}
}
int main()
{
Graf x;
x.citire();
x.bfs_darb_init();
fin.close();
fout.close();
return 0;
}