Pagini recente » Cod sursa (job #1620822) | Cod sursa (job #490329) | Cod sursa (job #106190) | Cod sursa (job #1804961) | Cod sursa (job #2811578)
#include <bits/stdc++.h>
#include<fstream>
#include<vector>
#include<map>
#include<queue>
int n, m, a, b, c;
class graf{
public:
std::vector< std::vector<int> > mat;
std::vector<std::vector<int> > lista;
std::vector<std::vector< std::pair<int, int>> > lista_cost;
std::vector< std::pair<int, int> > muchii;
void new_lista( int nod1, int nod2);
void new_lista_cost( int nod1, int nod2, int cost);
void afisare_lista_cost();
void solve_darb();
void afisare_mat(std::ostream &fg);
std::pair<int, int> BFS_darb(int start);
void afisare_lista();
};
void graf::new_lista(int nod1, int nod2){
lista[nod1].push_back(nod2);
lista[nod2].push_back(nod1);
}
void graf::new_lista_cost(int nod1, int nod2, int cost) {
lista_cost[nod1].push_back(std::make_pair(nod2, cost));
lista_cost[nod2].push_back(std::make_pair(nod1, cost));
}
void graf::afisare_lista_cost() {
for(auto i=1 ; i<n+1 ; i++){
std::cout<<i<<" - ";
for( auto j = lista_cost[i].begin() ; j != lista_cost[i].end(); j++){
std::cout<<" ( "<< j->first<<" , "<<j->second<<" ) ";
}
std::cout<<"\n";
}
std::cout<<"\n";
}
void graf::afisare_mat(std::ostream& fg) {
for(auto i=0; i<n; i++){
for(auto j=0 ; j<n; j++){
fg<<mat[i][j]<<" ";
}
fg<<"\n";
}
fg<<"\n";
}
void graf::afisare_lista() {
for(auto i=0 ; i<n ; i++){
std::cout<<i<<" : ";
for(auto j=0 ; j<lista[i].size(); j++)
std::cout<<lista[i][j]<<" ";
std::cout<<"\n";
}
std::cout<<"\n";
}
std::pair<int, int> graf::BFS_darb(int start){
std::vector<int> v;
std::vector<int> viz;
std::vector<int> dist;
std::queue<int> coada;
int diametru;
int dest;
for(int i = 0; i<n ; i++){
viz.push_back(-1);
dist.push_back(0);
}
viz[start] = 1;
coada.push(start);
dist[start] = 1;
while( !coada.empty()){
int nod = coada.front();
coada.pop();
for(auto vecin = lista[nod].begin() ; vecin != lista[nod].end(); vecin++){
if(viz[*vecin] == -1){
coada.push(*vecin);
viz[*vecin] = 1;
dist[*vecin] = dist[nod] + 1;
diametru = dist[*vecin];
dest = *vecin;
}
}
}
return std::make_pair(diametru, dest);
}
void graf::solve_darb() {
std::ifstream f("darb.in");
std::ofstream fg("darb.out");
f>>n;
std::vector<int> v;
int diametru, dest ;
std::pair<int, int> s;
for(int i = 0; i<n ; i++){
lista.push_back(v);
}
for( int i=0 ; i<n-1 ; i++){
f>>a>>b;
lista[a-1].push_back(b-1);
lista[b-1].push_back(a-1);
}
s = BFS_darb(0);
dest = s.second;
s = BFS_darb(dest);
diametru = s.first;
fg<<diametru;
}
int main() {
graf g;
g.solve_darb();
return 0;
}