Cod sursa(job #2811578)

Utilizator monicaandreea46Girbea Monica monicaandreea46 Data 2 decembrie 2021 17:21:18
Problema Diametrul unui arbore Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.9 kb
#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;
}