Cod sursa(job #2705564)

Utilizator DragosC1Dragos DragosC1 Data 12 februarie 2021 20:32:03
Problema Diametrul unui arbore Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.25 kb
#include <fstream>
#include <vector>
#include <iostream>
using namespace std;

bool viz[100001];
vector<int> a[100001];
int d[100001];
int n, leaf, Max, nivelMax;

void dfs(int x, int nivel) {
    int i;
    viz[x] = 1;
    for (i = 0; i < a[x].size(); i++)
        if (!viz[a[x][i]])
            dfs(a[x][i], nivel + 1);
    if (a[x].size() == 1 && nivel > nivelMax) {
        leaf = x;
        nivelMax = nivel;
    }
}

void bfs(int x) {
    int st, dr, Q[100001], i;
    st = dr = 0;
    Q[st] = x;
    viz[x] = 1;
    while (st <= dr) {
        x = Q[st++];
        for (i = 0; i < a[x].size(); i++)
            if (!viz[a[x][i]]) {
                Q[++dr] = a[x][i];
                viz[a[x][i]] = 1;
                d[a[x][i]] = d[x] + 1;
            }
    }
}

int main() {
    int i, x, y;

    ifstream f("darb.in");
    f >> n;
    for (i = 1; i < n; i++) {
        f >> x >> y;
        a[x].emplace_back(y);
        a[y].emplace_back(x);
    }
    f.close();
    
    dfs(1, 1);

    for (i = 1; i <= n; i++)
        viz[i] = 0;

    bfs(leaf);

    for (i = 1; i <= n; i++)
        if (d[i] > Max)
            Max = d[i];
    
    ofstream g("darb.out");
    g << Max + 1;
    g.close();

    return 0;
}