Cod sursa(job #2814153)

Utilizator redikusTiganus Alexandru redikus Data 7 decembrie 2021 17:39:16
Problema Diametrul unui arbore Scor 90
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 3.05 kb
#include <iostream>
#include <fstream>
#include <bits/stdc++.h>

using namespace std;

class graf {

protected:
    int noduri, muchii;
    vector < vector < int >> adiacenta;

public:
    // Constructor cu matrice de adiacenta data
    graf(vector < vector < int >> listaAdiacenta, int noduri, int muchii): adiacenta(listaAdiacenta), noduri(noduri), muchii(muchii) {};

    // Constructor fara matrice de adiacenta, se cu initalizeaza una goala
    graf(int noduri, int muchii): adiacenta(noduri + 1), noduri(noduri), muchii(muchii) {};

    vector < int > bfs(int);
    int dfs();

};

class graf_neorientat : public graf{
private:
    void dfsbiconex(int, vector < int >&, vector < int >&, stack < pair < int, int >>&, int&, vector < string >&);
    void dfsCriticalConnections(int tata, vector < int >&, vector < int >&, int&, vector < vector < int >>&, vector < int >&);
    vector < int > bfs(int, int&);

public:
    graf_neorientat(vector < vector < int >> listaAdiacenta, int noduri, int muchii): graf(listaAdiacenta, noduri, muchii) {};
    graf_neorientat(int noduri, int muchii): graf(noduri, muchii) {};

    friend istream& operator>>(istream&, graf_neorientat&);

    vector < string > biconex();

    vector < vector < int >> criticalConnections();

    int darb ();
};

istream& operator>>(istream& in, graf_neorientat& g) {
    for (int i = 0; i < g.muchii; i++) {
        int aux1, aux2;
        in >> aux1 >> aux2;
        g.adiacenta[aux1].push_back(aux2);
        g.adiacenta[aux2].push_back(aux1);
    }
    return in;
}

vector < int > graf_neorientat :: bfs(int start, int& finish) {
    vector < int > rasp(noduri + 1, -1);
    vector < int > vis(noduri + 1);
    queue < int > q;
    vis[start] = 1;
    q.push(start);
    rasp[start] = 0;

    // Se baga pe rand in queue toate nodurile nevizitate ale nodului din capul queue-ului, si se noteaza timpul la care se ajunge la ele
    while (!q.empty()) {
        int curr = q.front();
        q.pop();
        for (int i: adiacenta[curr]){
            if (vis[i] == 0) {
                vis[i] = 1;
                q.push(i);
                rasp[i] = rasp[curr] + 1;
                finish = i;
            }
        }
    }
    return rasp;
}

int graf_neorientat :: darb(){
    int m = 0, nod = 0, last = 0;
    vector<int> v(bfs(1, last));
//    for(int i = 1; i <= noduri; i++){
//        if(v[i] > m){
//            m = v[i];
//            nod = i;
//        }
//    }
    v = bfs(last, last);
    return v[last]+1;
}

void darbDriver() {
    // https://infoarena.ro/problema/darb
    // Citire
    ifstream in ("darb.in");
    ofstream out("darb.out");

    int n, m, a, b;
    in >> n;
    vector < vector < int >> listaAdiacenta(n + 1);

    while(in >> a >> b){
        listaAdiacenta[a].push_back(b);
        listaAdiacenta[b].push_back(a);
    }

    graf_neorientat x(listaAdiacenta, n, m);

    out << x.darb();
}

int main() {
    // Se apeleaza functia corespunzatoare problemei
    darbDriver();
    return 0;
}