Cod sursa(job #2853576)

Utilizator CiuiGinjoveanu Dragos Ciui Data 20 februarie 2022 13:52:22
Problema Diametrul unui arbore Scor 50
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 4.02 kb
#include <iostream>
#include <fstream>
#include <string>
#include <cstring>
#include <algorithm>
#include <utility>
#include <cmath>
#include <map>
#include <deque>
#include <vector>
#include <set>
#include <queue>
using namespace std;
 
ifstream fin("darb.in");
ofstream fout("darb.out");
 
const int MAX_SIZE = 100005;
vector<int> graph[MAX_SIZE];
int result = 0;
int lastPeak = 0;

void findMaximumDistances(int start) {
    int distances[MAX_SIZE];
    memset(distances, -1, MAX_SIZE);
    distances[start] = 1;
    queue<int> positions;
    positions.push(start);
    int maximum = 0;
    while (!positions.empty()) {
        int currentPeak = positions.front();
        positions.pop();
        if (1 == graph[currentPeak].size() && distances[currentPeak] == maximum) {
            lastPeak = currentPeak;
        }
        for (int i = 0; i < graph[currentPeak].size(); ++i) {
            int nextPeak = graph[currentPeak][i];
            if (distances[nextPeak] == -1) {
                distances[nextPeak] = distances[currentPeak] + 1;
                maximum = max(maximum, distances[nextPeak]);
                positions.push(nextPeak);
            }
        }
    }
    result = max(result, maximum);
}
 
int main() {
    int peaks;
    fin >> peaks;
    for (int i = 1; i <= peaks - 1; ++i) {
        int start, end;
        fin >> start >> end;
        graph[end].push_back(start);
        graph[start].push_back(end);
    }
    findMaximumDistances(1);
    findMaximumDistances(lastPeak);
    fout << result;
    return 0;
}

/*
 
 Salut! Revin la problema -> https://infoarena.ro/problema/darb
 Prima data am incercat sa implementez o solutie cu complexitatea O(N^2), si anume sa iau fiecare nod in parte si sa ma deplasez pe graf, afland distanta maxima pana la ultimul punct de pe graf (pornind de la un nod oarecare). Astfel, avand toate aceste distante, rezultatul pe care il cautam va fi distanta maxima dintre toate acestea.
 
 Trecand deja mai mult de 2 ore, am ales sa nu ma uit la solutia de rezolvare, ci doar la indicatiile problemei.
 Daca am inteles bine, ideea e sa pornesc de la un punct random si sa aflu ultimul punct de pe graf unde se va ajunge plecand de la punctul ales random. Apoi, sa plec de la punctul gasit cu inca o parcurgere catre ultimul punct de pe graf unde se va face deplasarea.
 
 Daca luam exemplul din problema si alegem punctul 10, ultimul punct de pe graf (cel mai indepartat) unde se va ajunge plecand de la acesta este "9" sau "8". Apoi, vrem sa plecam de la 9/8 catre ultimul punct de pe graf din nou, ajungand la 11. -> la a 2-a parcurgere, cea de la 9/8 la 11 se va trece prin 8 noduri, deci afisam 8.
 
 Implementare:
 Arborele va fi neorientat, deci in listele de adiacenta vom adauga si muchia de la x -> y, si cea de la y -> x.
 Apoi, am ales punctul random 1, ca punct de plecare pentru prima parcurgere. Am apelat o functie, unde vom avea, asemanator ca la BFS: un array de distante pentru fiecare punct in parte (pentru a marca totodata si daca ne-am deplasat deja pe un anumit punct) si o coada. Exact ca la BFS este principiul, cat timp coada nu e goala ne deplasam pe graf si aflam distantele de la punctul de start catre punctul de finish. Pentru a afla ultimul punct unde se va ajunge cu deplasarea, am pus o conditie ca daca punctul curent e adiacent doar cu un singur alt punct, atunci il vom stoca in variabila ("lastPeak") de fiecare data.
 !Aici cred ca am gresit cand am aflat care e cel mai indepartat punct unde se va ajunge.
 
 Dupa, mai apelam inca o data aceeasi functie, plecand de la lastPeak si afland distanta maxima parcursa pana un punct, distanta maxima fiind rezultatul.
 
 
 TESTE:
 
 11
 11 10
 1 10
 3 1
 3 2
 3 8
 8 9
 3 4
 4 5
 4 6
 6 7 -> 7 ok
 
 
 13
 1 2
 2 9
 1 4
 4 11
 11 12
 11 13
 1 5
 1 6
 1 7
 7 8
 1 3
 3 10 -> 6 ok
 
 11
 1 3
 3 6
 6 10
 10 11
 1 2
 2 5
 5 8
 5 9
 1 4
 4 7 -> 8 ok
 
 
 10
 1 2
 2 3
 3 4
 4 5
 5 6
 6 7
 7 8
 8 9
 9 10 -> 10 da
 
 
 11
 1 2
 1 3
 1 4
 2 5
 3 6
 4 7
 5 8
 5 9
 6 10
 10 11 -> 8 ok
 
 
 12
  11 1
  1 2
  2 4
  11 10
  10 3
  3 7
  11 9
  9 5
  5 12
  5 6
  11 8 -> 7 ok
 
 
 */