Pagini recente » Cod sursa (job #1032175) | Cod sursa (job #2555967) | Cod sursa (job #636621) | Cod sursa (job #393516) | Cod sursa (job #2812025)
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <stack>
#include <algorithm>
using namespace std;
ifstream in("darb.in");
ofstream out("darb.out");
const int nmax = 100001;
const int inf = 1<<30;
class Graf
{
private:
bool orientat;
int nrNoduri;
vector <int> listaAdiacenta[nmax];
vector <pair <int, int>> listaAdiacentaCost[nmax];
public:
Graf(int nrNoduri = 0, bool orientat = false);
void adaugaMuchie(int, int);
void adaugaMuchieCost(int, int, int);
void citireMuchii(int);
void citireMuchiiCost(int);
vector<int> BFS(int);
void DFS(int, bool*);
int nrComponenteConexe();
void DFSStiva(int nodcurent, bool *, stack<int> &);
void sortareTopologica();
void TarjanCTC(int&, int, int*, int*, bool*, stack <int> &, vector<vector<int>> &);
void CTC();
void TarjanBC(int&, int, int, int*, int*, stack <int>&, vector<vector<int>>&);
void BC();
void TarjanMC(int&, int, int, int*, int*, vector<pair<int,int>>&);
void MC();
vector <int> citireHakimi();
bool Hakimi(vector <int>);
vector <int> Dijkstra(int);
pair<int, vector <pair <int, int>>> Prim(int);
vector <int> BellmanFord(int);
void reuniune(int, int, vector<int>&, vector<int>&);
int gasire(int, vector<int>&);
void verifica(int, int, vector<int>&);
void paduri();
int diametru();
};
Graf :: Graf(int nrNoduri, bool orientat) : nrNoduri(nrNoduri), orientat(orientat)
{
this->nrNoduri = nrNoduri;
this->orientat = orientat;
}
void Graf:: adaugaMuchie(int nod1, int nod2)
{
listaAdiacenta[nod1].push_back(nod2);
}
void Graf::citireMuchii(int nrMuchii)
{
int nod1, nod2;
for(int i = 0; i < nrMuchii; i++)
{
in >> nod1 >> nod2;
listaAdiacenta[nod1].push_back(nod2);
if(!orientat)
{
listaAdiacenta[nod2].push_back(nod1);
}
}
}
vector<int> Graf::BFS(int start)
{
queue <int> coadaBFS;
int vizitatBFS[nmax] = {false};
vector <int> distantaBFS(nmax);
fill(distantaBFS.begin(), distantaBFS.end(), 0);
coadaBFS.push(start);
vizitatBFS[start] = true;
distantaBFS[start] = 1;
while(!coadaBFS.empty())
{
int nodCurent = coadaBFS.front();
coadaBFS.pop();
for(auto vecin:listaAdiacenta[nodCurent])
{
if(!vizitatBFS[vecin])
{
vizitatBFS[vecin] = true;
distantaBFS[vecin] = distantaBFS[nodCurent] + 1;
coadaBFS.push(vecin);
}
}
}
return distantaBFS;
}
int Graf::diametru()
{
vector <int> distante(nmax);
distante = BFS(1);
int distantaMaxima = -1, nodMaxim;
for(int i = 1; i <= nrNoduri; i++)
{
if(distante[i] > distantaMaxima)
{
distantaMaxima = distante[i];
nodMaxim = i;
}
}
distante = BFS(nodMaxim);
distantaMaxima = -1;
for(int i = 1; i <= nrNoduri; i++)
{
if(distante[i] > distantaMaxima)
{
distantaMaxima = distante[i];
}
}
return distantaMaxima;
}
int main() {
int n, m;
in >> n;
Graf g(n,false);
g.citireMuchii(n - 1);
int rezultat = g.diametru();
out << rezultat;
return 0;
}